제출 #1000533

#제출 시각아이디문제언어결과실행 시간메모리
1000533shenfe1게임 (IOI13_game)C++17
63 / 100
13080 ms23960 KiB
#include "game.h" #include <bits/stdc++.h> #pragma optimize("Ofast") #pragma target("avx2") using namespace std; #define ll long long #define ld long double #define pb push_back #define pf push_front #define pii pair<int,int> #define all(v) v.begin(),v.end() #define F first #define S second #define mem(a,i) memset(a,i,sizeof(a)) #define sz(s) (int)s.size() #define y1 yy #define ppb pop_back #define lb lower_bound #define ub upper_bound #define gcd(a,b) __gcd(a,b) #define in insert // #define int ll const int MAX=22000+15; const int N=104; const ll inf=1e9; const int mod=1e9+7; const int mod1=1e9+9; const ld eps=1e-9; int dx[8]={1,0,-1,0,1,-1,-1,1}; int dy[8]={0,1,0,-1,1,-1,1,-1}; mt19937 rng(21345678); int binpow(int a,int n){ if(!n)return 1; if(n%2==1)return a*binpow(a,n-1)%mod; int k=binpow(a,n/2); return k*k%mod; } long long gcd2(long long X, long long Y) { long long tmp=0; while (X != Y && Y != 0) { tmp = X; X = Y; Y = tmp % Y; } return X; } int n,m; struct node{ ll g,G; int key; int prior; node *l=0,*r=0; node(int X,ll k){ key=X; g=k; G=k; prior=rng(); } }; typedef node *pnode; ll g(pnode a){ if(!a)return 0; return a->g; } void upd(pnode a){ if(!a)return; a->g=gcd2(gcd2(g(a->l),g(a->r)),a->G); } pnode mrg(pnode a,pnode b){ if(!a)return b; if(!b)return a; if(a->prior>b->prior){ a->r=mrg(a->r,b); upd(a); return a; } else{ b->l=mrg(a,b->l); upd(b); return b; } } pair<pnode,pnode> split(pnode a,int x){ if(!a)return {0,0}; if(a->key<=x){ pair<pnode,pnode> res=split(a->r,x); a->r=res.F; upd(a); return {a,res.S}; } else{ pair<pnode,pnode> res=split(a->l,x); a->l=res.S; upd(a); return {res.F,a}; } } pnode t[60*MAX]; int CNT; vector<int> lv,rv; void new_node(){ lv.pb(0); rv.pb(0); } pnode update(pnode a,int posy,ll x){ pair<pnode,pnode> A=split(a,posy-1); pair<pnode,pnode> B=split(A.S,posy); pnode bf=new node(posy,x); A.F=mrg(A.F,bf); A.F=mrg(A.F,B.S); return A.F; } ll get(pnode a,int l,int r){ if(!a)return 0; pair<pnode,pnode> A=split(a,l-1); pair<pnode,pnode> B=split(A.S,r); ll ans=0; if(B.F){ ans=B.F->g; } a=mrg(B.F,B.S); a=mrg(A.F,a); return ans; } void out(pnode a){ if(!a)return; out(a->l); cout<<a->G<<" "; out(a->r); } void update(int v,int tl,int tr,int posx,int posy,ll x){ // cerr<<v<<" "<<tl<<" "<<tr<<"\n"; // cerr<<"TREAP "; // if(t[v])out(t[v]); // cerr<<"\n"; if(tl==tr){ // return; t[v]=update(t[v],posy,x); return; } int tm=(tl+tr)/2; if(posx<=tm){ if(!lv[v]){ lv[v]=CNT++; new_node(); } update(lv[v],tl,tm,posx,posy,x); } else{ if(!rv[v]){ rv[v]=CNT++; new_node(); } update(rv[v],tm+1,tr,posx,posy,x); } ll ans=0; if(lv[v])ans=gcd(ans,get(t[lv[v]],posy,posy)); if(rv[v])ans=gcd(ans,get(t[rv[v]],posy,posy)); // cout<<v<<" "<<tl<<" "<<tr<<" "<<posy<<" "<<ans<<"\n"; t[v]=update(t[v],posy,ans); // out(t[v]); // cout<<"\n"; } ll get(int v,int tl,int tr,int lx,int rx,int ly,int ry){ if(lx>rx||lx>tr||tl>rx)return 0; if(lx<=tl&&tr<=rx){ // cout<<tl<<" "<<tr<<" "<<ly<<" "<<ry<<" "<<get(t[v],ly,ry)<<"\n"; return get(t[v],ly,ry); } int tm=(tl+tr)/2; ll ans=0; if(lv[v])ans=gcd(ans,get(lv[v],tl,tm,lx,rx,ly,ry)); if(rv[v])ans=gcd(ans,get(rv[v],tm+1,tr,lx,rx,ly,ry)); return ans; } void outAl(int v,int tl,int tr){ // cout<<v<<" "<<tl<<" "<<tr<<"\n"; // out(t[v]); // cout<<"\n"; if(tl==tr){ // cout<<"! "<<tl<<"\n"; // out(t[v]); // cout<<"\n"; return; } int tm=(tl+tr)/2; if(lv[v])outAl(lv[v],tl,tm); if(rv[v])outAl(rv[v],tm+1,tr); } void init(int R, int C) { n=R-1; m=C-1; CNT=1; mem(t,0); lv.pb(0); rv.pb(0); } void update(int P, int Q, long long K) { // return; // cerr<<P<<" "<<Q<<" "<<K<<"\n"; update(0,0,n,P,Q,K); } long long calculate(int P, int Q, int U, int V) { // cerr<<"ZAPROS\n"; // return 0; outAl(0,0,n); int lx=min(P,U); int rx=max(P,U); int ly=min(Q,V); int ry=max(Q,V); return get(0,0,n,lx,rx,ly,ry); }

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

game.cpp:5: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    5 | #pragma optimize("Ofast")
      | 
game.cpp:6: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    6 | #pragma target("avx2")
      | 
game.cpp: In function 'void upd(pnode)':
game.cpp:83:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   83 |   if(!a)return;
      |   ^~
game.cpp:84:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   84 |  a->g=gcd2(gcd2(g(a->l),g(a->r)),a->G);
      |  ^
#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...