Submission #960347

#	Time	Username	Problem	Language	Result	Execution time	Memory
960347		shenfe1	Game (IOI13_game)	C++17	0 / 100	31 ms	38236 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=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=10;

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]=gcd2(t[vx][v],t[vx][ly[vx][v]]);
  if(ry[vx][v])t[vx][v]=gcd2(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=gcd2(res,gety(vx,ly[vx][v],tl,tm,l,r));
  if(ry[vx][v])res=gcd2(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){
    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);
  }
  int res=0;
  if(lx[v])res=gcd2(res,gety(lx[v],0,0,m,posy,posy));
  if(rx[v])res=gcd2(res,gety(rx[v],0,0,m,posy,posy));
  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){
    return gety(v,0,0,m,ly,ry);
  }
  int tm=(tl+tr)/2;
  int 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;
  for(int i=0;i<MAX*L;i++){
    t[i].pb(0);
    ly[i].pb(0);
    ry[i].pb(0);
  }
}
 
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);
}

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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20