Submission #337634

#TimeUsernameProblemLanguageResultExecution timeMemory
337634talant117408Weighting stones (IZhO11_stones)C++17
100 / 100
75 ms5656 KiB
/* Code written by Talant I.D. */ #pragma GCC optimize("Ofast") #include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //using namespace __gnu_pbds; using namespace std; //typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define precision(n) fixed << setprecision(n) #define pb push_back #define ub upper_bound #define lb lower_bound #define mp make_pair #define eps (double)1e-9 #define PI 2*acos(0.0) #define endl "\n" #define sz(v) int((v).size()) #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define OK cout << "OK" << endl; inline bool isvowel(char ch){ ch = tolower(ch); return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'); } inline bool isprime(int n){ if(n < 2 || (n%2 == 0 && n != 2)) return false; for(int i = 3; i*i <= n; i++) if(n%i == 0) return false; return true; } class Union{ private: vector <int> saizu, link; public: Union(int n){ saizu.assign(n, 1); link.resize(n); iota(all(link), 0); } int find(int n){ if(link[n] == n) return n; return link[n] = find(link[n]); } int same(int a, int b){ return find(a) == find(b); } void unite(int a, int b){ if(same(a, b)) return; a = find(a); b = find(b); if(saizu[a] < saizu[b]) swap(a, b); saizu[a] += saizu[b]; link[b] = a; } int getsize(int a){ return saizu[find(a)]; } }; const int mod = 1e9+7; ll mode(ll a){ a %= mod; if(a < 0) a += mod; return a; } ll subt(ll a, ll b){ return mode(mode(a)-mode(b)); } ll add(ll a, ll b){ return mode(mode(a)+mode(b)); } ll mult(ll a, ll b){ return mode(mode(a)*mode(b)); } ll binpow(ll a, ll b){ ll res = 1; while(b){ if(b&1) res = mult(res, a); a = mult(a, a); b >>= 1; } return res; } const int N = 1e5+7; int tree[2][N*4], lz[2][N*4]; void push(int v, int l, int r){ tree[0][v] += lz[0][v]; tree[1][v] += lz[1][v]; if(l != r){ lz[0][v<<1] += lz[0][v]; lz[0][(v<<1)+1] += lz[0][v]; lz[1][v<<1] += lz[1][v]; lz[1][(v<<1)+1] += lz[1][v]; } lz[0][v] = lz[1][v] = 0; } void update(int v, int l, int r, int ql, int qr, int val){ push(v, l, r); if(l > qr || ql > r) return ; if(ql <= l && r <= qr){ tree[0][v] += val; tree[1][v] += val; if(l != r){ lz[0][v<<1] += val; lz[0][(v<<1)+1] += val; lz[1][v<<1] += val; lz[1][(v<<1)+1] += val; } return ; } int mid = (l+r) >> 1; update(v<<1, l, mid, ql, qr, val); update((v<<1)+1, mid+1, r, ql, qr, val); tree[0][v] = min(tree[0][v<<1], tree[0][(v<<1)+1]); tree[1][v] = max(tree[1][v<<1], tree[1][(v<<1)+1]); } int main(){ do_not_disturb int n; cin >> n; for(int i = 0; i < n; i++){ int x, type; cin >> x >> type; if(type == 1) update(1, 1, n, 1, x, 1); else update(1, 1, n, 1, x, -1); auto fi = tree[1][1], sc = tree[0][1]; if(fi > 0){ if(sc >= 0) cout << ">" << endl; else cout << "?" << endl; } else{ if(sc <= 0) cout << "<" << endl; else cout << "?" << endl; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...