제출 #960359

#제출 시각아이디문제언어결과실행 시간메모리
960359shenfe1게임 (IOI13_game)C++17
80 / 100
3374 ms256000 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}; 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; while (X != Y && Y != 0) { tmp = X; X = Y; Y = tmp % Y; } return X; } const int L=40; vector<ll> t[MAX*L]; vector<int> ly[MAX*L],ry[MAX*L]; int cx=0; int lx[MAX*L],rx[MAX*L]; int n,m; void updatey(int vx,int v,int tl,int tr,int pos,ll x){ if(tl==tr){ t[vx][v]=x; return; } int tm=(tl+tr)/2; if(pos<=tm){ if(!ly[vx][v]){ ly[vx][v]=sz(t[vx]); t[vx].pb(0); ly[vx].pb(0); ry[vx].pb(0); } updatey(vx,ly[vx][v],tl,tm,pos,x); } else{ if(!ry[vx][v]){ ry[vx][v]=sz(t[vx]); t[vx].pb(0); ly[vx].pb(0); ry[vx].pb(0); } updatey(vx,ry[vx][v],tm+1,tr,pos,x); } t[vx][v]=0; if(ly[vx][v])t[vx][v]=gcd(t[vx][v],t[vx][ly[vx][v]]); if(ry[vx][v])t[vx][v]=gcd(t[vx][v],t[vx][ry[vx][v]]); } ll gety(int vx,int v,int tl,int tr,int l,int r){ if(l>r||tl>r||l>tr)return 0; if(l<=tl&&tr<=r){ return t[vx][v]; } int tm=(tl+tr)/2; ll res=0; if(ly[vx][v])res=gcd(res,gety(vx,ly[vx][v],tl,tm,l,r)); if(ry[vx][v])res=gcd(res,gety(vx,ry[vx][v],tm+1,tr,l,r)); return res; } void updatex(int v,int tl,int tr,int posx,int posy,ll x){ if(tl==tr){ if(t[v].empty()){ t[v].pb(0); ly[v].pb(0); ry[v].pb(0); } updatey(v,0,0,m,posy,x); return; } int tm=(tl+tr)/2; if(posx<=tm){ if(!lx[v]){ lx[v]=++cx; } updatex(lx[v],tl,tm,posx,posy,x); } else{ if(!rx[v]){ rx[v]=++cx; } updatex(rx[v],tm+1,tr,posx,posy,x); } ll res=0; if(lx[v])res=gcd(res,gety(lx[v],0,0,m,posy,posy)); if(rx[v])res=gcd(res,gety(rx[v],0,0,m,posy,posy)); if(t[v].empty()){ t[v].pb(0); ly[v].pb(0); ry[v].pb(0); } updatey(v,0,0,m,posy,res); } ll getx(int v,int tl,int tr,int xl,int xr,int ly,int ry){ if(xl>xr||tl>xr||xl>tr)return 0; if(xl<=tl&&tr<=xr){ if(t[v].empty())return 0; return gety(v,0,0,m,ly,ry); } int tm=(tl+tr)/2; ll res=0; if(lx[v])res=gcd(res,getx(lx[v],tl,tm,xl,xr,ly,ry)); if(rx[v])res=gcd(res,getx(rx[v],tm+1,tr,xl,xr,ly,ry)); return res; } void init(int R, int C) { n=R-1; m=C-1; } void update(int P, int Q, long long K) { updatex(0,0,n,P,Q,K); } long long calculate(int P, int Q, int U, int V) { // return 0; int lx=min(P,U); int rx=max(P,U); int ly=min(Q,V); int ry=max(Q,V); return getx(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")
      |
#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...