제출 #141997

#제출 시각아이디문제언어결과실행 시간메모리
141997liwiGame (IOI13_game)C++11
100 / 100
5824 ms65760 KiB
#include "game.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; #define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0) char _; #define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end()) #define all(a) a.begin(),a.end() #define println printf("\n"); #define readln(x) getline(cin,x); #define pb push_back #define endl "\n" #define INT_INF 0x3f3f3f3f #define LL_INF 0x3f3f3f3f3f3f3f3f #define MOD 1000000007 #define mp make_pair #define fastio cin.tie(0); cin.sync_with_stdio(0); typedef unsigned long long ull; typedef long long ll; typedef long double ld; typedef unordered_map<int,int> umii; typedef pair<int,int> pii; typedef pair<double,double> pdd; typedef pair<ll,ll> pll; typedef pair<int,pii> triple; typedef int8_t byte; mt19937 g1(time(0)); int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);} ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);} ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);} ll lcm(ll a, ll b){return a*b/gcd(a,b);} ll fpow(ll b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;} ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;} template<typename T> struct node{ T val; ll prior,gg; int mn,mx; node *l,*r; node(T v){ val = v, gg = val.second, mn = mx = val.first; prior = randlong(-1e18,1e18); l = r = 0; } }; template<typename T> struct SMTreap{ node<T> *rt=0; inline ll ggcd(node<T> *&n){return n?n->gg:0;} inline void upd_gcd(node<T> *&n){if(n)n->gg=gcd(gcd(ggcd(n->l),ggcd(n->r)),n->val.second);} inline void upd(node<T> *&n){ if(!n) return; if(n->l) n->mn = n->l->mn; else n->mn = n->val.first; if(n->r) n->mx = n->r->mx; else n->mx = n->val.first; upd_gcd(n); } bool contains(int col){ node<T> *n = rt; while(n){ if(n->val.first == col) return true; n = (n->val.first<col?n->r:n->l); } return false; } void split(node<T> *n, T key, node<T> *&l, node<T> *&r){ if(!n) l = r = 0; else if(key < n->val) split(n->l,key,l,n->l), r = n; else split(n->r,key,n->r,r), l = n; upd(n); } void merge(node<T> *&n, node<T> *l, node<T> *r){ if(!l || !r) n = l?l:r; else if(l->prior > r->prior) merge(l->r,l->r,r), n = l; else merge(r->l,l,r->l), n = r; upd(n); } void replace(node<T> *&n, int col, ll v){ if(n->val.first == col) n->val.second = v; else replace(n->val.first<col?n->r:n->l,col,v); upd(n); } void insert(node<T> *v){ if(contains(v->val.first)) replace(rt,v->val.first,v->val.second); else{ node<T> *t1=0,*t2=0; split(rt,v->val,t1,t2); merge(t1,t1,v); merge(rt,t1,t2); } } void erase(node<T> *&n, T v){ if(!n) return; if(n->val == v) merge(n,n->l,n->r); else erase(v<n->val?n->l:n->r,v); upd(n); } T kth(node<T> *&n, int idx){ if(gsz(n->l)+1 == idx) return n->val; else if(gsz(n->l) >= idx) return kth(n->l,idx); return kth(n->r,idx-gsz(n->l)-1); } // ll range_query(node<T> *&n, int l, int r){ // if(!rt) return 0; // node<T> *t1=0,*t2=0,*t3=0; // split(rt,mp(l,-1),t1,t2); // split(t2,mp(r+1,-1),t2,t3); // ll ans = ggcd(t2); // merge(rt,t1,t2); // merge(rt,rt,t3); // return ans; // } ll range_query(node<T> *&n, int l, int r){ if(!n) return 0; if(n->mx < l || n->mn > r) return 0; if(l <= n->mn && r >= n->mx) return n->gg; ll ret = (n->val.first >= l && n->val.first <= r)?n->val.second:0; if(n->l) ret = gcd(ret,range_query(n->l,l,r)); if(n->r) ret = gcd(ret,range_query(n->r,l,r)); return ret; } }; struct snode{ int l,r; SMTreap<pair<int,ll>> s; snode *lft,*rgt; snode(int l, int r){ this->l = l; this->r = r; lft = rgt = 0; } void push_up(int col){ ll gg = gcd(lft?lft->s.range_query(lft->s.rt,col,col):0,rgt?rgt->s.range_query(rgt->s.rt,col,col):0); s.insert(new node<pair<int,ll>>(mp(col,gg))); } void update(int row, int col, ll val){ if(l == r){ s.insert(new node<pair<int,ll>>(mp(col,val))); return; } int mid = (l+r)/2; if(row <= mid){ if(!lft) lft = new snode(l,mid); lft->update(row,col,val); }else{ if(!rgt) rgt = new snode(mid+1,r); rgt->update(row,col,val); } push_up(col); } ll query(int rl, int rr, int cl, int cr){ if(l == rl && r == rr) return s.range_query(s.rt,cl,cr); int mid = (l+r)/2; if(rr <= mid){ if(!lft) return 0; return lft->query(rl,rr,cl,cr); }else if(rl > mid){ if(!rgt) return 0; return rgt->query(rl,rr,cl,cr); }else{ ll f = !lft?0:lft->query(rl,mid,cl,cr); ll s = !rgt?0:rgt->query(mid+1,rr,cl,cr); return gcd(f,s); } } }; int num_rows,num_cols; snode *seg; void init(int R, int C){ num_rows = R, num_cols = C; seg = new snode(1,R); } void update(int P, int Q, ll K){ P++, Q++; seg->update(P,Q,K); } ll calculate(int r1, int c1, int r2, int c2){ r1++, c1++, r2++, c2++; return seg->query(r1,r2,c1,c2); } void print(){ for(int i=1; i<=num_rows; i++){ for(int k=1; k<=num_cols; k++) printf("%lld ",seg->query(i,i,k,k)); printf("\n"); } printf("\n"); }

컴파일 시 표준 에러 (stderr) 메시지

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...