Submission #960281

#	Time	Username	Problem	Language	Result	Execution time	Memory
960281		shenfe1	Game (IOI13_game)	C++17	63 / 100	3660 ms	256000 KiB

game

#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=10000+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=10;
 
map<pii,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 xl,int xr,int v,int tl,int tr,int posx,int posy,ll x){
  // cout<<vx<<" "<<xl<<" "<<xr<<" "<<v<<" "<<tl<<" "<<tr<<" "<<sz(t[vx])<<"\n";
  // return;
  if(tl==tr){
    if(xl==xr){
      t[vx][{tl,tr}]=x;
    }
    else{
      t[vx][{tl,tr}]=0;
      if(lx[vx]&&t[lx[vx]].count({tl,tr}))t[vx][{tl,tr}]=gcd2(t[vx][{tl,tr}],t[lx[vx]][{tl,tr}]);
      if(rx[vx]&&t[rx[vx]].count({tl,tr}))t[vx][{tl,tr}]=gcd2(t[vx][{tl,tr}],t[rx[vx]][{tl,tr}]);
    }
    return;
  }
  int tm=(tl+tr)/2;
  if(posy<=tm){
    if(ly[vx][v]==0){
      ly[vx][v]=sz(t[vx]);
      t[vx][{tl,tm}]=0;
      ly[vx].pb(0);
      ry[vx].pb(0);
    }
    updatey(vx,xl,xr,ly[vx][v],tl,tm,posx,posy,x);
  }
  else{
    if(ry[vx][v]==0){
      ry[vx][v]=sz(t[vx]);
      t[vx][{tm+1,tr}]=0;
      ly[vx].pb(0);
      ry[vx].pb(0);
    }
    updatey(vx,xl,xr,ry[vx][v],tm+1,tr,posx,posy,x);
  }
  t[vx][{tl,tr}]=0;
  if(ly[vx][v])t[vx][{tl,tr}]=gcd2(t[vx][{tl,tr}],t[vx][{tl,tm}]);
  if(ry[vx][v])t[vx][{tl,tr}]=gcd2(t[vx][{tl,tr}],t[vx][{tm+1,tr}]);
  // cout<<xl<<" "<<xr<<" "<<tl<<" "<<tr<<" "<<t[vx][{tl,tr}]<<"\n";
}
 
void updatex(int v,int tl,int tr,int posx,int posy,ll x){
  if(tl!=tr){
    int tm=(tl+tr)/2;
    if(posx<=tm){
      if(lx[v]==0)lx[v]=++cx;
      updatex(lx[v],tl,tm,posx,posy,x);
    }
    else{
      if(rx[v]==0)rx[v]=++cx;
      updatex(rx[v],tm+1,tr,posx,posy,x);
    }
  }
  if(t[v].empty()){
    t[v][{0,m}]=0;
    ly[v].pb(0);
    ry[v].pb(0);
  }
  updatey(v,tl,tr,0,0,m,posx,posy,x);
}
 
ll gety(int vx,int xl,int xr,int v,int tl,int tr,int l,int r){
  if(l>r||tl>r||l>tr)return 0;
  if(l<=tl&&tr<=r){
    // cout<<v<<" "<<sz(t[vx])<<" "<<sz(ly[vx])<<" "<<sz(ry[vx])<<"\n";
    // cout<<xl<<" "<<xr<<" "<<tl<<" "<<tr<<" "<<t[vx][v]<<"\n";
    return t[vx][{tl,tr}];
  }
  int tm=(tl+tr)/2;
  ll res=0;
  if(ly[vx][v])res=gcd2(res,gety(vx,xl,xr,ly[vx][v],tl,tm,l,r));
  if(ry[vx][v])res=gcd2(res,gety(vx,xl,xr,ry[vx][v],tm+1,tr,l,r));
  return 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 gety(v,xl,xr,0,0,m,ly,ry);
    return 0;
  }
  int tm=(tl+tr)/2;
  ll res=0;
  if(lx[v])res=gcd2(res,getx(lx[v],tl,tm,xl,xr,ly,ry));
  if(rx[v])res=gcd2(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) {
  // return;
  // cout<<K<<"\n";
  updatex(0,0,n,P,Q,K);
}
 
long long calculate(int P, int Q, int U, int V) {
  // return 2;
  int lx=min(P,U);
  int rx=max(P,U);
  int ly=min(Q,V);
  int ry=max(Q,V);
  // cout<<lx<<" "<<rx<<" "<<ly<<" "<<ry<<"\n";
  // return 1;
  return getx(0,0,n,lx,rx,ly,ry);
}

Compilation message (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")
      |

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20