| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 40957 |
2018-02-10T13:29:41 Z |
RockyB |
Editor (BOI15_edi) |
C++14 |
|
3000 ms |
169316 KB |
/// In The Name Of God
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define nl '\n'
#define ioi exit(0);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = (int)3e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
using namespace std;
inline int readChar();
template <class T = int> inline T readInt();
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x );
inline void writeWord( const char *s );
/** Read */
static const int buf_size = 4096;
inline int getChar() {
static char buf[buf_size];
static int len = 0, pos = 0;
if (pos == len) {
pos = 0, len = fread(buf, 1, buf_size, stdin);
}
if (pos == len) {
return -1;
}
return buf[pos++];
}
inline int readChar() {
int c = getChar();
while (c <= 32) {
c = getChar();
}
return c;
}
template <class T>
inline T readInt() {
int s = 1, c = readChar();
T x = 0;
if (c == '-')
s = -1, c = getChar();
while ('0' <= c && c <= '9')
x = x * 10 + c - '0', c = getChar();
return s == 1 ? x : -x;
}
/** Write */
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar( int x ) {
if (write_pos == buf_size)
fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt( T x, char end ) {
if (x < 0)
writeChar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n)
s[n++] = '0' + x % 10, x /= 10;
while (n--)
writeChar(s[n]);
if (end)
writeChar(end);
}
inline void writeWord( const char *s ) { while (*s)
writeChar(*s++); }
struct Flusher {
~Flusher() {
if (write_pos)
fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
}
} flusher;
int n;
int type[N], to[N];
bool ok[N];
int Total;
bool edit[N];
struct tree {
int t[N << 2];
set <int> z[N << 2];
void upd(int p, int x, int v = 1, int tl = 0, int tr = n) {
if (tl == tr) {
if (x < 0) {
//if (!sz(z[v])) ioi
Total--;
z[v].erase(-x);
}
else z[v].insert(x), Total++;
if (sz(z[v])) t[v] = *z[v].rbegin();
else t[v] = 0;
return;
}
int tm = tl + tr >> 1;
if (p <= tm) upd(p, x, v << 1, tl, tm);
else upd(p, x, v << 1 | 1, tm + 1, tr);
t[v] = max(t[v << 1], t[v << 1 | 1]);
}
int get(int l, int r, int v = 1, int tl = 0, int tr = n) {
if (l <= tl && tr <= r) return t[v];
if (tl > r || tr < l) return 0;
int tm = tl + tr >> 1;
return max(get(l, r, v << 1, tl, tm), get(l, r, v << 1 | 1, tm + 1, tr));
}
} f;
static const int Sz = N * 40;
int sz;
int root[Sz], t[Sz], ls[Sz], rs[Sz], cnt[Sz];
void build(int &v, int tl = 1, int tr = n + 1) {
v = ++sz;
if (tl == tr) {
if (tl == 1) cnt[v] = 1;
return;
}
int tm = tl + tr >> 1;
build(ls[v], tl, tm);
build(rs[v], tm + 1, tr);
cnt[v] = cnt[ls[v]] + cnt[rs[v]];
}
void upd(int p, int x, int &v, int lv, int tl = 1, int tr = n + 1) {
v = ++sz;
if (tl == tr) {
t[v] = x;
cnt[v] = cnt[lv] + 1;
return;
}
int tm = (tl + tr) >> 1;
if (p <= tm) {
upd(p, x, ls[v], ls[lv], tl, tm);
rs[v] = rs[lv];
}
else {
upd(p, x, rs[v], rs[lv], tm + 1, tr);
ls[v] = ls[lv];
}
cnt[v] = cnt[ls[v]] + cnt[rs[v]];
}
void del(int p, int &v, int lv, int tl = 1, int tr = n + 1) {
v = ++sz;
if (tl == tr) {
t[v] = 0;
cnt[v] = cnt[lv] - 1;
return;
}
int tm = (tl + tr) >> 1;
if (p <= tm) {
del(p, ls[v], ls[lv], tl, tm);
rs[v] = rs[lv];
}
else {
del(p, rs[v], rs[lv], tm + 1, tr);
ls[v] = ls[lv];
}
cnt[v] = cnt[ls[v]] + cnt[rs[v]];
}
int get(int x, int v, int tl = 1, int tr = n + 1) {
if (tl == tr) return t[v];
int tm = (tl + tr) >> 1;
if (cnt[ls[v]] >= x) return get(x, ls[v], tl, tm);
return get(x - cnt[ls[v]], rs[v], tm + 1, tr);
}
int total(int p) {
return cnt[root[p]];
}
set <int> st;
int main() {
#ifdef IOI2018
freopen ("in.txt", "r", stdin);
//freopen ("slow.out", "w", stdout);
#endif
n = readInt();
build(root[0]);
for (int i = 1; i <= n; i++) {
type[i] = readInt();
if (type[i] > 0) {
int now = total(i - 1);
upd(now + 1, type[i], root[i], root[i - 1]);
ok[i] = 1;
st.insert(i);
edit[i] = 1;
}
else {
type[i] = -type[i];
int p = -1;
if (!sz(st)) {
p = f.get(0, type[i] - 1);
}
else {
p = max(*st.rbegin(), f.get(0, type[i] - 1));
}
to[i] = p;
int cnt = 0;
while (1) {
ok[p] ^= 1;
if (!ok[p]) {
if (!edit[p]) f.upd(type[p], -p);
else st.erase(p);
}
else {
if (!edit[p]) f.upd(type[p], p);
else st.insert(p);
}
if (!to[p]) break;
p = to[p];
}
root[i] = root[p];
if (!ok[p]) del(total(i), root[i], root[p]);
ok[i] = 1;
f.upd(type[i], i);
}
writeInt(get(total(i), root[i]));
writeChar('\n');
}
ioi
}
Compilation message
edi.cpp: In member function 'void tree::upd(int, int, int, int, int)':
edi.cpp:139:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int tm = tl + tr >> 1;
^
edi.cpp: In member function 'int tree::get(int, int, int, int, int)':
edi.cpp:147:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int tm = tl + tr >> 1;
^
edi.cpp: In function 'void build(int&, int, int)':
edi.cpp:161:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int tm = tl + tr >> 1;
^
edi.cpp: In function 'int main()':
edi.cpp:239:8: warning: unused variable 'cnt' [-Wunused-variable]
int cnt = 0;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
56696 KB |
Output is correct |
| 2 |
Correct |
52 ms |
58080 KB |
Output is correct |
| 3 |
Correct |
47 ms |
58080 KB |
Output is correct |
| 4 |
Correct |
49 ms |
58080 KB |
Output is correct |
| 5 |
Correct |
493 ms |
58100 KB |
Output is correct |
| 6 |
Correct |
48 ms |
58100 KB |
Output is correct |
| 7 |
Correct |
56 ms |
58552 KB |
Output is correct |
| 8 |
Correct |
47 ms |
58552 KB |
Output is correct |
| 9 |
Correct |
51 ms |
58568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
296 ms |
167908 KB |
Output is correct |
| 2 |
Correct |
285 ms |
169316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
250 ms |
169316 KB |
Output is correct |
| 2 |
Execution timed out |
3091 ms |
169316 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
56696 KB |
Output is correct |
| 2 |
Correct |
52 ms |
58080 KB |
Output is correct |
| 3 |
Correct |
47 ms |
58080 KB |
Output is correct |
| 4 |
Correct |
49 ms |
58080 KB |
Output is correct |
| 5 |
Correct |
493 ms |
58100 KB |
Output is correct |
| 6 |
Correct |
48 ms |
58100 KB |
Output is correct |
| 7 |
Correct |
56 ms |
58552 KB |
Output is correct |
| 8 |
Correct |
47 ms |
58552 KB |
Output is correct |
| 9 |
Correct |
51 ms |
58568 KB |
Output is correct |
| 10 |
Correct |
296 ms |
167908 KB |
Output is correct |
| 11 |
Correct |
285 ms |
169316 KB |
Output is correct |
| 12 |
Correct |
250 ms |
169316 KB |
Output is correct |
| 13 |
Execution timed out |
3091 ms |
169316 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
