oj.uz

Submission #258787

# Submission time Handle Problem Language Result Execution time Memory
258787 2020-08-06T14:44:36 Z davi_bart Game (IOI13_game) C++14
63 / 100
 3000 ms 256004 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define ll long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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 ll dim=1<<30;
class segment{
  public:
  struct node{
    ll val,left,right;
    node(){
      val=0;
      left=right=-1;
    }
  };
  vector<node> s=vector<node>(1);
  node def;
  ll upd(ll pos,ll l,ll r,ll p,ll v){
    if(l>p || r<p)return s[pos].val;
    if(l==r)return s[pos].val=v;
    ll x=0,y=0;
    if(s[pos].left==-1){
      s[pos].left=s.size();
      s.push_back(def);
    }
    if(s[pos].right==-1){
      s[pos].right=s.size();
      s.push_back(def);
    }

    if(p<=(l+r)/2){
      if(s[pos].left==-1){
        s[pos].left=s.size();
        s.push_back(def);
      }
      if(s[pos].right!=-1)y=upd(s[pos].right,(l+r)/2+1,r,p,v);
      x=upd(s[pos].left,l,(l+r)/2,p,v);
    }else{
      if(s[pos].right==-1){
        s[pos].right=s.size();
        s.push_back(def);
      }
      if(s[pos].left!=-1)x=upd(s[pos].left,l,(l+r)/2,p,v);
      y=upd(s[pos].right,(l+r)/2+1,r,p,v);
    }
    return s[pos].val=gcd2(x,y);
  }
  ll query(ll pos,ll l,ll r,ll a,ll b){
    if(b<l || r<a)return 0;
    if(a<=l && r<=b){
        return s[pos].val;
    }
    ll sx=0,dx=0;
    if(s[pos].left!=-1)sx=query(s[pos].left,l,(l+r)/2,a,b);
    if(s[pos].right!=-1)dx=query(s[pos].right,(l+r)/2+1,r,a,b);
    return gcd2(sx,dx);
  }
};
class segofseg{
  public:
  struct node{
    ll left,right;
    segment k;
    node(){
      left=right=-1;
    }
  };
  vector<node> s=vector<node>(1);
  node def;
  void upd(ll pos,ll l,ll r,ll p,ll q,ll v){
    if(l>p || r<p)return ;
    if(l==r){
      s[pos].k.upd(0,0,dim-1,q,v);
      return;
    }
    ll x=0,y=0;
    if(p<=(l+r)/2){
      if(s[pos].left==-1){
        s[pos].left=s.size();
        s.push_back(def);
      }
      upd(s[pos].left,l,(l+r)/2,p,q,v);
    }else{
      if(s[pos].right==-1){
        s[pos].right=s.size();
        s.push_back(def);
      }
      upd(s[pos].right,(l+r)/2+1,r,p,q,v);
    }

    if(s[pos].left!=-1)x=s[s[pos].left].k.query(0,0,dim-1,q,q);
    if(s[pos].right!=-1)y=s[s[pos].right].k.query(0,0,dim-1,q,q);
    s[pos].k.upd(0,0,dim-1,q,gcd2(x,y));
  }
  ll query(ll pos,ll l,ll r,ll a,ll b,ll x,ll y){
    if(b<l || r<a)return 0;
    if(a<=l && r<=b){
        return s[pos].k.query(0,0,dim-1,x,y);
    }
    ll sx=0,dx=0;
    if(s[pos].left!=-1)sx=query(s[pos].left,l,(l+r)/2,a,b,x,y);
    if(s[pos].right!=-1)dx=query(s[pos].right,(l+r)/2+1,r,a,b,x,y);
    return gcd2(sx,dx);
  }
}tot;
void init(int R, int C) {
}

void update(int P, int Q, long long K){
  tot.upd(0,0,dim-1,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
  return tot.query(0,0,dim-1,P,U,Q,V);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 4 ms 896 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 4 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 8 ms 896 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 0 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1316 ms 66756 KB Output is correct
5 Correct 1064 ms 65736 KB Output is correct
6 Correct 1502 ms 64224 KB Output is correct
7 Correct 1230 ms 63780 KB Output is correct
8 Correct 848 ms 42352 KB Output is correct
9 Correct 1225 ms 65000 KB Output is correct
10 Correct 1209 ms 63968 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 4 ms 896 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 4 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 2124 ms 31116 KB Output is correct
13 Correct 2864 ms 16500 KB Output is correct
14 Correct 905 ms 5496 KB Output is correct
15 Correct 3000 ms 24104 KB Output is correct
16 Correct 1304 ms 42160 KB Output is correct
17 Correct 1848 ms 30564 KB Output is correct
18 Correct 2506 ms 43764 KB Output is correct
19 Correct 2382 ms 43792 KB Output is correct
20 Correct 2226 ms 42900 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 7 ms 896 KB Output is correct
3 Correct 4 ms 896 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 1184 ms 66976 KB Output is correct
13 Correct 993 ms 65984 KB Output is correct
14 Correct 1197 ms 64520 KB Output is correct
15 Correct 1177 ms 63892 KB Output is correct
16 Correct 768 ms 42752 KB Output is correct
17 Correct 1365 ms 65020 KB Output is correct
18 Correct 1169 ms 64096 KB Output is correct
19 Correct 2005 ms 31360 KB Output is correct
20 Correct 2568 ms 16760 KB Output is correct
21 Correct 862 ms 5732 KB Output is correct
22 Correct 2856 ms 23980 KB Output is correct
23 Correct 1070 ms 42352 KB Output is correct
24 Correct 1619 ms 30324 KB Output is correct
25 Correct 2477 ms 42868 KB Output is correct
26 Correct 2346 ms 42840 KB Output is correct
27 Correct 2200 ms 42096 KB Output is correct
28 Runtime error 690 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 4 ms 896 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 4 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4 ms 896 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1191 ms 66324 KB Output is correct
13 Correct 1062 ms 65484 KB Output is correct
14 Correct 1213 ms 63896 KB Output is correct
15 Correct 1203 ms 63296 KB Output is correct
16 Correct 800 ms 41808 KB Output is correct
17 Correct 1444 ms 64464 KB Output is correct
18 Correct 1151 ms 63556 KB Output is correct
19 Correct 1949 ms 30848 KB Output is correct
20 Correct 2586 ms 16452 KB Output is correct
21 Correct 870 ms 4856 KB Output is correct
22 Correct 2735 ms 23416 KB Output is correct
23 Correct 1014 ms 41844 KB Output is correct
24 Correct 1646 ms 29492 KB Output is correct
25 Correct 2565 ms 41728 KB Output is correct
26 Correct 2402 ms 41688 KB Output is correct
27 Correct 2275 ms 41204 KB Output is correct
28 Runtime error 694 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -