oj.uz

답안 #1000535

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1000535 2024-06-17T16:39:31 Z shenfe1 게임 (IOI13_game) C++17
100 / 100
 3364 ms 58824 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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