# 14221: 【原4221】战士

### 题目描述

author: Shuhao Li 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4221

## Sample Input

``````5
4 0
3 1
2 0
1 0
5 0
``````

## Sample Output

``````2
``````

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/4/10.
//

//
// Created by BugenZhao on 2019/4/5.
//

#ifndef SBL_BSTACK_H
#define SBL_BSTACK_H

template<typename Item>
class BStack {
class Node {
public:
Item item;
Node *next;

explicit Node(const Item &item, Node *next = nullptr) : item(item), next(next) {}

explicit Node(Node *next = nullptr) : next(next) {}

virtual ~Node() = default;
};

int N;
Node *top;

public:
BStack() {
top = nullptr;
N = 0;
}

void push(const Item &item) {
top = new Node{item, top};
++N;
}

Item peek() {
}

Item pop() {
Node *tmp = top;
Item ret = top->item;
top = top->next;
delete tmp;
--N;
return ret;
}

int size() {
return N;
}

void clear() {
Node *tmp;
while (top) {
tmp = top;
top = top->next;
delete tmp;
}
top = nullptr;
N = 0;
}

bool isEmpty() {
}

virtual ~BStack() {
Node *tmp;
while (top) {
tmp = top;
top = top->next;
delete tmp;
}
}

private:
class Iterator {
Node *it;
Node *top;
public:

Iterator(Node *top) : it(top), top(top) {}

bool hasNext() const {
return it != nullptr;
}

Item &next() {
Node *p = it;
it = it->next;
return p->item;
}

const Item &next() const {
Node *p = it;
it = it->next;
return p->item;
}
};

public:
Iterator iterator() const {
return Iterator(top);
}
};

#endif //SBL_BSTACK_H

class S {
public:
int power;
bool dir;
};

#include <iostream>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

int N;
cin >> N;

BStack<S> stack;

int power;
bool dir;
for (int i = 0; i < N; ++i) {
cin >> power >> dir;

while (!stack.isEmpty()) {
if (stack.peek().dir == 0 || stack.peek().dir == dir) {
stack.push(S{power, dir});
break;
} else {
if (stack.peek().power >= power) {
break;
} else {
stack.pop();
}

}
}
if (stack.isEmpty()) {
stack.push(S{power, dir});
}
}
cout << stack.size() << endl;
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "stack"
#include "cstdio"
using namespace std;

stack<int> stack_data;

int main() {
int n;
scanf("%d", &n);

int ans = 0;
for (int i = 0; i < n; ++i) {
int val, direction;
scanf("%d %d", &val, &direction);
if (direction) {
stack_data.push(val);
}
else {
while (!stack_data.empty()) {
if (val >= stack_data.top())
stack_data.pop();
else {
--ans;
break;
}
}
++ans;
}
}
printf("%d", (int)stack_data.size() + ans);

return 0;
}
``````

## skyzh's solution

``````#include <iostream>
#include <cstdio>
using namespace std;

int val[500003] = { 0 };
int dir[500003] = { 0 };

template <typename T>
class Stack {
public:
T *data;
int top_ptr;
Stack(int cap) : data(new T[cap]), top_ptr(0) {}
~Stack() { delete[] data; }
void push(const T& d) { data[top_ptr++] = d; }
T pop() { return data[--top_ptr]; }
T top() { return data[top_ptr - 1]; }
};

int main() {
int n;
scanf("%d", &n);
int l_ans = 0;
for (int i = 0; i < n; i++) scanf("%d%d", &val[i], &dir[i]);
Stack <int> x(500003);
for (int i = n - 1; i >= 0; i--) {
if (dir[i] == 0) {
x.push(val[i]);
} else {
while (!x.empty() && val[i] > x.top()) {
x.pop();
}
if (x.empty()) ++l_ans;
}
}
printf("%d\n", l_ans + x.top_ptr);
return 0;
}
``````