Submission #1000535

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1000535	2024-06-17T16:39:31 Z	shenfe1	Game (IOI13_game)	C++17	100 / 100	3364 ms	58824 KB

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

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	10584 KB	Output is correct
2	Correct	6 ms	10584 KB	Output is correct
3	Correct	5 ms	10588 KB	Output is correct
4	Correct	4 ms	10588 KB	Output is correct
5	Correct	4 ms	10588 KB	Output is correct
6	Correct	6 ms	10732 KB	Output is correct
7	Correct	7 ms	10684 KB	Output is correct
8	Correct	5 ms	10584 KB	Output is correct
9	Correct	4 ms	10688 KB	Output is correct
10	Correct	4 ms	10588 KB	Output is correct
11	Correct	4 ms	10588 KB	Output is correct
12	Correct	4 ms	10588 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	10588 KB	Output is correct
2	Correct	4 ms	10588 KB	Output is correct
3	Correct	4 ms	10588 KB	Output is correct
4	Correct	561 ms	20500 KB	Output is correct
5	Correct	267 ms	20456 KB	Output is correct
6	Correct	797 ms	17744 KB	Output is correct
7	Correct	919 ms	17440 KB	Output is correct
8	Correct	617 ms	16936 KB	Output is correct
9	Correct	913 ms	17400 KB	Output is correct
10	Correct	709 ms	17064 KB	Output is correct
11	Correct	4 ms	10588 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	10584 KB	Output is correct
2	Correct	5 ms	10588 KB	Output is correct
3	Correct	5 ms	10588 KB	Output is correct
4	Correct	4 ms	10588 KB	Output is correct
5	Correct	4 ms	10716 KB	Output is correct
6	Correct	5 ms	10584 KB	Output is correct
7	Correct	5 ms	10588 KB	Output is correct
8	Correct	6 ms	10588 KB	Output is correct
9	Correct	4 ms	10764 KB	Output is correct
10	Correct	5 ms	10588 KB	Output is correct
11	Correct	4 ms	10588 KB	Output is correct
12	Correct	905 ms	23124 KB	Output is correct
13	Correct	1660 ms	19752 KB	Output is correct
14	Correct	271 ms	20656 KB	Output is correct
15	Correct	1739 ms	21160 KB	Output is correct
16	Correct	287 ms	20576 KB	Output is correct
17	Correct	1260 ms	18936 KB	Output is correct
18	Correct	2067 ms	22392 KB	Output is correct
19	Correct	1886 ms	22664 KB	Output is correct
20	Correct	1756 ms	21384 KB	Output is correct
21	Correct	5 ms	10588 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	10588 KB	Output is correct
2	Correct	5 ms	10740 KB	Output is correct
3	Correct	5 ms	10588 KB	Output is correct
4	Correct	4 ms	10588 KB	Output is correct
5	Correct	4 ms	10616 KB	Output is correct
6	Correct	4 ms	10588 KB	Output is correct
7	Correct	4 ms	10588 KB	Output is correct
8	Correct	5 ms	10588 KB	Output is correct
9	Correct	4 ms	10588 KB	Output is correct
10	Correct	4 ms	10588 KB	Output is correct
11	Correct	5 ms	10584 KB	Output is correct
12	Correct	620 ms	20564 KB	Output is correct
13	Correct	311 ms	20308 KB	Output is correct
14	Correct	844 ms	17748 KB	Output is correct
15	Correct	991 ms	18172 KB	Output is correct
16	Correct	609 ms	17292 KB	Output is correct
17	Correct	907 ms	18340 KB	Output is correct
18	Correct	734 ms	17888 KB	Output is correct
19	Correct	969 ms	24036 KB	Output is correct
20	Correct	1715 ms	19756 KB	Output is correct
21	Correct	280 ms	20848 KB	Output is correct
22	Correct	1769 ms	20992 KB	Output is correct
23	Correct	291 ms	20508 KB	Output is correct
24	Correct	1284 ms	18392 KB	Output is correct
25	Correct	2093 ms	21792 KB	Output is correct
26	Correct	1787 ms	21788 KB	Output is correct
27	Correct	1640 ms	21292 KB	Output is correct
28	Correct	673 ms	36956 KB	Output is correct
29	Correct	1331 ms	40244 KB	Output is correct
30	Correct	2210 ms	33344 KB	Output is correct
31	Correct	1869 ms	33536 KB	Output is correct
32	Correct	390 ms	35044 KB	Output is correct
33	Correct	605 ms	34972 KB	Output is correct
34	Correct	358 ms	34100 KB	Output is correct
35	Correct	1388 ms	29676 KB	Output is correct
36	Correct	2578 ms	38200 KB	Output is correct
37	Correct	2076 ms	38512 KB	Output is correct
38	Correct	1932 ms	37796 KB	Output is correct
39	Correct	1771 ms	34332 KB	Output is correct
40	Correct	4 ms	10588 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	10588 KB	Output is correct
2	Correct	5 ms	10588 KB	Output is correct
3	Correct	6 ms	10844 KB	Output is correct
4	Correct	4 ms	10588 KB	Output is correct
5	Correct	4 ms	10588 KB	Output is correct
6	Correct	4 ms	10588 KB	Output is correct
7	Correct	4 ms	10588 KB	Output is correct
8	Correct	4 ms	10584 KB	Output is correct
9	Correct	5 ms	10588 KB	Output is correct
10	Correct	4 ms	10588 KB	Output is correct
11	Correct	4 ms	10588 KB	Output is correct
12	Correct	567 ms	20644 KB	Output is correct
13	Correct	269 ms	20316 KB	Output is correct
14	Correct	756 ms	17748 KB	Output is correct
15	Correct	903 ms	17352 KB	Output is correct
16	Correct	573 ms	16720 KB	Output is correct
17	Correct	847 ms	17560 KB	Output is correct
18	Correct	685 ms	16996 KB	Output is correct
19	Correct	875 ms	23152 KB	Output is correct
20	Correct	1649 ms	19940 KB	Output is correct
21	Correct	273 ms	20588 KB	Output is correct
22	Correct	1648 ms	20808 KB	Output is correct
23	Correct	281 ms	20560 KB	Output is correct
24	Correct	1248 ms	18436 KB	Output is correct
25	Correct	2088 ms	21588 KB	Output is correct
26	Correct	1811 ms	20436 KB	Output is correct
27	Correct	1542 ms	19800 KB	Output is correct
28	Correct	579 ms	34104 KB	Output is correct
29	Correct	1252 ms	40244 KB	Output is correct
30	Correct	2135 ms	33568 KB	Output is correct
31	Correct	1937 ms	33316 KB	Output is correct
32	Correct	391 ms	34896 KB	Output is correct
33	Correct	558 ms	35032 KB	Output is correct
34	Correct	351 ms	34040 KB	Output is correct
35	Correct	1378 ms	29760 KB	Output is correct
36	Correct	2533 ms	38408 KB	Output is correct
37	Correct	2153 ms	38452 KB	Output is correct
38	Correct	1938 ms	37876 KB	Output is correct
39	Correct	965 ms	56616 KB	Output is correct
40	Correct	2290 ms	58824 KB	Output is correct
41	Correct	3364 ms	52016 KB	Output is correct
42	Correct	3074 ms	51784 KB	Output is correct
43	Correct	754 ms	53548 KB	Output is correct
44	Correct	704 ms	52820 KB	Output is correct
45	Correct	1729 ms	34276 KB	Output is correct
46	Correct	3145 ms	57388 KB	Output is correct
47	Correct	3115 ms	57384 KB	Output is correct
48	Correct	2825 ms	57012 KB	Output is correct
49	Correct	4 ms	10588 KB	Output is correct