Submission #40957

#	Time	Username	Problem	Language	Result	Execution time	Memory
40957		RockyB	Editor (BOI15_edi)	C++14	35 / 100	3091 ms	169316 KiB

edi

/// 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 (stderr)

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;
        ^

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37