Submission #685656

#TimeUsernameProblemLanguageResultExecution timeMemory
685656Ronin13Weighting stones (IZhO11_stones)C++14
100 / 100
80 ms24744 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define f first #define s second #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define epb emplace_back using namespace std; const int nmax = 5e5 + 1; struct node{ int sum, mn, mx; node(){ sum = 0; mx = -1e9; mn = 1e9; } node(int val){ sum = val; mx = val; mn = val; } }t[4 * nmax]; node merg(node a, node b){ node c; c.sum = a.sum + b.sum; c.mn = min(a.mn + b.sum, b.mn); c.mx = max(a.mx + b.sum, b.mx); return c; } void update(int v, int l, int r, int pos, int val){ if(l > pos || r < pos) return; if(l == r){ t[v] = {val}; return; } int m = (l + r) / 2; update(2 * v, l, m, pos, val); update(2 * v + 1, m + 1, r, pos, val); t[v] = merg(t[2 * v], t[2 * v + 1]); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); pii mx = {0, 0}; int n; cin >> n; for(int i = 1; i <= n; i++){ int x, y; cin >> x >> y; if(y == 1) update(1, 1, n, x, 1); else update(1, 1, n, x, -1); if(mx.f < x) mx = {x, y}; if(mx.s == 1){ if(t[1].mn >= 0) cout << '>'; else cout << '?'; } else{ //cout << t[1].mx << "\n"; if(t[1].mx <= 0) cout << '<'; else cout << '?'; } cout << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...