Submission #1000535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000535		shenfe1	Game (IOI13_game)	C++17	100 / 100	3364 ms	58824 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};
 
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);
}

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")
      | 
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);
      |  ^

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