oj.uz

Submission #968971

# Submission time Handle Problem Language Result Execution time Memory
968971 2024-04-24T10:31:40 Z shenfe1 Game (IOI13_game) C++17
63 / 100
 5632 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};

mt19937 rng(21345678);

int n,m;

struct DO1{
  vector<ll> t;
  unordered_map<int,int> lv,rv;

  DO1(){
    t.pb(0);
  }

  void update(int v,int tl,int tr,int pos,ll x){
    if(tl==tr){
      t[v]=x;
      return;
    }
    int tm=(tl+tr)/2;
    if(pos<=tm){
      if(!lv[v]){
        lv[v]=sz(t);
        t.pb(0);
      }
      update(lv[v],tl,tm,pos,x);
    }
    else{
      if(!rv.count(v)){
        rv[v]=sz(t);
        t.pb(0);
      }
      update(rv[v],tm+1,tr,pos,x);
    }
    t[v]=0;
    if(lv.count(v))t[v]=gcd(t[v],t[lv[v]]);
    if(rv.count(v))t[v]=gcd(t[v],t[rv[v]]);
  }

  ll get(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[v];
    }
    int tm=(tl+tr)/2;
    ll ans=0;
    if(lv.count(v))ans=gcd(ans,get(lv[v],tl,tm,l,r));
    if(rv.count(v))ans=gcd(ans,get(rv[v],tm+1,tr,l,r));
    return ans;
  }
};

struct DO2{

  vector<DO1> t;
  unordered_map<int,int> lv,rv;

  DO2(){
    t.emplace_back();
  }

  void new_node(){
    t.emplace_back();
  }

  void update(int v,int tl,int tr,int posx,int posy,ll x){
    if(tl==tr){
      t[v].update(0,0,m,posy,x);
      return;
    }
    int tm=(tl+tr)/2;
    if(posx<=tm){
      if(!lv.count(v)){
        lv[v]=sz(t);
        new_node();
      }
      update(lv[v],tl,tm,posx,posy,x);
    }
    else{
      if(!rv.count(v)){
        rv[v]=sz(t);
        new_node();
      }
      update(rv[v],tm+1,tr,posx,posy,x);
    }
    ll ans=0;
    if(lv.count(v))ans=gcd(ans,t[lv[v]].get(0,0,m,posy,posy));
    if(rv.count(v))ans=gcd(ans,t[rv[v]].get(0,0,m,posy,posy));
    t[v].update(0,0,m,posy,ans);
  }

  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){
      return t[v].get(0,0,m,ly,ry);
    }
    int tm=(tl+tr)/2;
    ll ans=0;
    if(lv.count(v))ans=gcd(ans,get(lv[v],tl,tm,lx,rx,ly,ry));
    if(rv.count(v))ans=gcd(ans,get(rv[v],tm+1,tr,lx,rx,ly,ry));
    return ans;
  }
}t;

void init(int R, int C) {
  n=R-1;
  m=C-1;
}
 
void update(int P, int Q, long long K) {
  t.update(0,0,n,P,Q,K);
}
 
long long calculate(int P, int Q, int U, int V) {
  int lx=min(P,U);
  int rx=max(P,U);
  int ly=min(Q,V);
  int ry=max(Q,V);
  return t.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")
      |

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 668 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 444 KB Output is correct
4 Correct 1490 ms 22352 KB Output is correct
5 Correct 1027 ms 22104 KB Output is correct
6 Correct 1046 ms 19948 KB Output is correct
7 Correct 1308 ms 19744 KB Output is correct
8 Correct 682 ms 14028 KB Output is correct
9 Correct 1226 ms 19936 KB Output is correct
10 Correct 1153 ms 19440 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2926 ms 28368 KB Output is correct
13 Correct 3662 ms 14028 KB Output is correct
14 Correct 501 ms 5872 KB Output is correct
15 Correct 4672 ms 19088 KB Output is correct
16 Correct 561 ms 35384 KB Output is correct
17 Correct 2269 ms 24028 KB Output is correct
18 Correct 5226 ms 36716 KB Output is correct
19 Correct 4200 ms 36876 KB Output is correct
20 Correct 4447 ms 36312 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1665 ms 22504 KB Output is correct
13 Correct 1044 ms 22152 KB Output is correct
14 Correct 1249 ms 19716 KB Output is correct
15 Correct 1586 ms 19680 KB Output is correct
16 Correct 718 ms 14296 KB Output is correct
17 Correct 1365 ms 19740 KB Output is correct
18 Correct 1483 ms 19116 KB Output is correct
19 Correct 3195 ms 28540 KB Output is correct
20 Correct 3831 ms 13928 KB Output is correct
21 Correct 523 ms 5856 KB Output is correct
22 Correct 4864 ms 19092 KB Output is correct
23 Correct 550 ms 35600 KB Output is correct
24 Correct 2289 ms 24024 KB Output is correct
25 Correct 5386 ms 36844 KB Output is correct
26 Correct 4128 ms 36944 KB Output is correct
27 Correct 4220 ms 36268 KB Output is correct
28 Runtime error 1470 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 1 ms 348 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 548 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1714 ms 22332 KB Output is correct
13 Correct 1191 ms 22312 KB Output is correct
14 Correct 1208 ms 19716 KB Output is correct
15 Correct 1459 ms 19656 KB Output is correct
16 Correct 699 ms 13948 KB Output is correct
17 Correct 1362 ms 19712 KB Output is correct
18 Correct 1431 ms 19272 KB Output is correct
19 Correct 3131 ms 28536 KB Output is correct
20 Correct 3961 ms 13760 KB Output is correct
21 Correct 533 ms 5716 KB Output is correct
22 Correct 4809 ms 19176 KB Output is correct
23 Correct 557 ms 35368 KB Output is correct
24 Correct 2131 ms 23832 KB Output is correct
25 Correct 5632 ms 36848 KB Output is correct
26 Correct 3568 ms 37232 KB Output is correct
27 Correct 3822 ms 36336 KB Output is correct
28 Runtime error 1470 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -