oj.uz

Submission #959100

# Submission time Handle Problem Language Result Execution time Memory
959100 2024-04-07T13:33:12 Z vjudge1 Game (IOI13_game) C++17
63 / 100
 3826 ms 256000 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};

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

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 22616 KB Output is correct
2 Correct 7 ms 22876 KB Output is correct
3 Correct 7 ms 22876 KB Output is correct
4 Correct 6 ms 22672 KB Output is correct
5 Correct 6 ms 22620 KB Output is correct
6 Correct 8 ms 22876 KB Output is correct
7 Correct 6 ms 22452 KB Output is correct
8 Correct 5 ms 22616 KB Output is correct
9 Correct 7 ms 22872 KB Output is correct
10 Correct 6 ms 22620 KB Output is correct
11 Correct 6 ms 22620 KB Output is correct
12 Correct 5 ms 22620 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22620 KB Output is correct
2 Correct 5 ms 22620 KB Output is correct
3 Correct 5 ms 22692 KB Output is correct
4 Correct 1640 ms 49944 KB Output is correct
5 Correct 1173 ms 49832 KB Output is correct
6 Correct 1243 ms 47404 KB Output is correct
7 Correct 1503 ms 47240 KB Output is correct
8 Correct 658 ms 39148 KB Output is correct
9 Correct 1389 ms 47416 KB Output is correct
10 Correct 1483 ms 46828 KB Output is correct
11 Correct 5 ms 22620 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22616 KB Output is correct
2 Correct 7 ms 22940 KB Output is correct
3 Correct 8 ms 22928 KB Output is correct
4 Correct 5 ms 22620 KB Output is correct
5 Correct 6 ms 22620 KB Output is correct
6 Correct 7 ms 22876 KB Output is correct
7 Correct 5 ms 22676 KB Output is correct
8 Correct 7 ms 22676 KB Output is correct
9 Correct 7 ms 22876 KB Output is correct
10 Correct 7 ms 22624 KB Output is correct
11 Correct 6 ms 22676 KB Output is correct
12 Correct 2490 ms 57752 KB Output is correct
13 Correct 3297 ms 39300 KB Output is correct
14 Correct 426 ms 28048 KB Output is correct
15 Correct 3826 ms 45928 KB Output is correct
16 Correct 846 ms 67996 KB Output is correct
17 Correct 1547 ms 52056 KB Output is correct
18 Correct 3517 ms 69420 KB Output is correct
19 Correct 2933 ms 69608 KB Output is correct
20 Correct 3007 ms 68852 KB Output is correct
21 Correct 5 ms 22620 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22620 KB Output is correct
2 Correct 11 ms 23128 KB Output is correct
3 Correct 7 ms 22876 KB Output is correct
4 Correct 5 ms 22620 KB Output is correct
5 Correct 5 ms 22616 KB Output is correct
6 Correct 7 ms 22876 KB Output is correct
7 Correct 6 ms 22620 KB Output is correct
8 Correct 6 ms 22616 KB Output is correct
9 Correct 8 ms 22876 KB Output is correct
10 Correct 7 ms 22708 KB Output is correct
11 Correct 6 ms 22620 KB Output is correct
12 Correct 1679 ms 49872 KB Output is correct
13 Correct 1147 ms 49708 KB Output is correct
14 Correct 1236 ms 47540 KB Output is correct
15 Correct 1638 ms 47280 KB Output is correct
16 Correct 655 ms 39292 KB Output is correct
17 Correct 1497 ms 47512 KB Output is correct
18 Correct 1510 ms 46824 KB Output is correct
19 Correct 2500 ms 57560 KB Output is correct
20 Correct 3069 ms 39084 KB Output is correct
21 Correct 381 ms 28500 KB Output is correct
22 Correct 3753 ms 45744 KB Output is correct
23 Correct 852 ms 68160 KB Output is correct
24 Correct 1600 ms 51864 KB Output is correct
25 Correct 3516 ms 69464 KB Output is correct
26 Correct 2764 ms 69460 KB Output is correct
27 Correct 2872 ms 68872 KB Output is correct
28 Runtime error 930 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 22616 KB Output is correct
2 Correct 8 ms 22876 KB Output is correct
3 Correct 8 ms 22876 KB Output is correct
4 Correct 6 ms 22620 KB Output is correct
5 Correct 5 ms 22620 KB Output is correct
6 Correct 7 ms 22876 KB Output is correct
7 Correct 6 ms 22620 KB Output is correct
8 Correct 6 ms 22620 KB Output is correct
9 Correct 7 ms 22876 KB Output is correct
10 Correct 6 ms 22620 KB Output is correct
11 Correct 7 ms 22620 KB Output is correct
12 Correct 1640 ms 50320 KB Output is correct
13 Correct 1160 ms 49952 KB Output is correct
14 Correct 1312 ms 47548 KB Output is correct
15 Correct 1564 ms 47592 KB Output is correct
16 Correct 665 ms 39196 KB Output is correct
17 Correct 1543 ms 47260 KB Output is correct
18 Correct 1623 ms 46972 KB Output is correct
19 Correct 2607 ms 57808 KB Output is correct
20 Correct 3347 ms 39100 KB Output is correct
21 Correct 374 ms 28112 KB Output is correct
22 Correct 3651 ms 45740 KB Output is correct
23 Correct 805 ms 68112 KB Output is correct
24 Correct 1469 ms 51820 KB Output is correct
25 Correct 3478 ms 69432 KB Output is correct
26 Correct 2803 ms 69604 KB Output is correct
27 Correct 2746 ms 68864 KB Output is correct
28 Runtime error 889 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -