oj.uz

Submission #258791

# Submission time Handle Problem Language Result Execution time Memory
258791 2020-08-06T14:47:46 Z davi_bart Game (IOI13_game) C++14
80 / 100
 3607 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());
const ll dim=1<<30;
class segment{
  public:
  struct node{
    ll val;
    int left,right;
    node(){
      val=0;
      left=right=-1;
    }
  };
  vector<node> s=vector<node>(1);
  node def;
  ll upd(int pos,int l,int r,int 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(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=__gcd(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 __gcd(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,__gcd(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 __gcd(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 1 ms 384 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 964 ms 30224 KB Output is correct
5 Correct 781 ms 30832 KB Output is correct
6 Correct 945 ms 26996 KB Output is correct
7 Correct 989 ms 26880 KB Output is correct
8 Correct 635 ms 17496 KB Output is correct
9 Correct 968 ms 26784 KB Output is correct
10 Correct 1215 ms 25948 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 1 ms 384 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1543 ms 15992 KB Output is correct
13 Correct 2094 ms 7992 KB Output is correct
14 Correct 709 ms 2680 KB Output is correct
15 Correct 2538 ms 10976 KB Output is correct
16 Correct 763 ms 18168 KB Output is correct
17 Correct 1177 ms 13176 KB Output is correct
18 Correct 1817 ms 18388 KB Output is correct
19 Correct 1655 ms 18420 KB Output is correct
20 Correct 1604 ms 17916 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 640 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 512 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 991 ms 29868 KB Output is correct
13 Correct 791 ms 30820 KB Output is correct
14 Correct 930 ms 26916 KB Output is correct
15 Correct 970 ms 26732 KB Output is correct
16 Correct 646 ms 17496 KB Output is correct
17 Correct 1010 ms 26736 KB Output is correct
18 Correct 891 ms 25956 KB Output is correct
19 Correct 1535 ms 15864 KB Output is correct
20 Correct 2109 ms 7800 KB Output is correct
21 Correct 638 ms 2408 KB Output is correct
22 Correct 2422 ms 10744 KB Output is correct
23 Correct 793 ms 18100 KB Output is correct
24 Correct 1172 ms 13048 KB Output is correct
25 Correct 1778 ms 19020 KB Output is correct
26 Correct 1606 ms 19216 KB Output is correct
27 Correct 1534 ms 18328 KB Output is correct
28 Correct 899 ms 161196 KB Output is correct
29 Correct 1983 ms 177804 KB Output is correct
30 Correct 3607 ms 127964 KB Output is correct
31 Correct 3412 ms 104360 KB Output is correct
32 Correct 620 ms 10448 KB Output is correct
33 Correct 864 ms 12792 KB Output is correct
34 Correct 934 ms 171172 KB Output is correct
35 Correct 1294 ms 93752 KB Output is correct
36 Correct 2274 ms 175412 KB Output is correct
37 Correct 2090 ms 175492 KB Output is correct
38 Correct 2045 ms 174944 KB Output is correct
39 Correct 1705 ms 137504 KB Output is correct
40 Correct 1 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 3 ms 640 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 512 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 947 ms 30416 KB Output is correct
13 Correct 776 ms 30568 KB Output is correct
14 Correct 953 ms 27416 KB Output is correct
15 Correct 1014 ms 27112 KB Output is correct
16 Correct 662 ms 17752 KB Output is correct
17 Correct 995 ms 26980 KB Output is correct
18 Correct 942 ms 26344 KB Output is correct
19 Correct 1528 ms 15992 KB Output is correct
20 Correct 2110 ms 7672 KB Output is correct
21 Correct 684 ms 2680 KB Output is correct
22 Correct 2342 ms 11084 KB Output is correct
23 Correct 773 ms 18424 KB Output is correct
24 Correct 1157 ms 13688 KB Output is correct
25 Correct 1771 ms 19400 KB Output is correct
26 Correct 1646 ms 19240 KB Output is correct
27 Correct 1627 ms 18532 KB Output is correct
28 Correct 892 ms 161268 KB Output is correct
29 Correct 1785 ms 177484 KB Output is correct
30 Correct 3585 ms 127868 KB Output is correct
31 Correct 3346 ms 104384 KB Output is correct
32 Correct 571 ms 10488 KB Output is correct
33 Correct 754 ms 12896 KB Output is correct
34 Correct 953 ms 171172 KB Output is correct
35 Correct 1286 ms 93556 KB Output is correct
36 Correct 2339 ms 175120 KB Output is correct
37 Correct 2049 ms 175304 KB Output is correct
38 Correct 1954 ms 174996 KB Output is correct
39 Runtime error 1048 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -