Submission #444880

#TimeUsernameProblemLanguageResultExecution timeMemory
444880JovanBWeighting stones (IZhO11_stones)C++17
100 / 100
65 ms6520 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define pb push_back struct Segment{ int val[1000005], open[1000005], closed[1000005]; Segment(){ } void mrg(int node){ int g = min(open[node*2], closed[node*2+1]); open[node] = open[node*2] + open[node*2+1]- g; closed[node] = closed[node*2] + closed[node*2+1] - g; val[node] = val[node*2] + val[node*2+1] + g; } void upd(int node, int l, int r, int x, int g){ if(l == r){ if(g == -1) open[node] = 1; else closed[node] = 1; return; } int mid = (l+r)/2; if(x <= mid) upd(node*2, l, mid, x, g); else upd(node*2+1, mid+1, r, x, g); mrg(node); } }; int main(){ ios_base::sync_with_stdio(false), cin.tie(0); cout.precision(10); cout << fixed; int n; cin >> n; Segment *prvi = new Segment(); Segment *drugi = new Segment(); int prvih = 0, drugih = 0; for(int i=1; i<=n; i++){ int a, b; cin >> a >> b; if(b == 1){ prvih++; prvi->upd(1, 1, n, a, -1); drugi->upd(1, 1, n, a, 1); } else{ drugih++; prvi->upd(1, 1, n, a, 1); drugi->upd(1, 1, n, a, -1); } if(prvi->val[1] == prvih) cout << "<\n"; else if(drugi->val[1] == drugih) cout << ">\n"; else cout << "?\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...