oj.uz

Submission #258821

# Submission time Handle Problem Language Result Execution time Memory
258821 2020-08-06T15:09:01 Z davi_bart Game (IOI13_game) C++14
80 / 100
 3378 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;
  void upd(int pos,int l,int r,int p,ll v){
    if(l>p || r<p)return ;
    if(l==r){
        s[pos].val=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);
      }
      if(s[pos].right!=-1)y=s[s[pos].right].val;
      upd(s[pos].left,l,(l+r)/2,p,v);
      x=s[s[pos].left].val;
    }else{
      if(s[pos].right==-1){
        s[pos].right=s.size();
        s.push_back(def);
      }
      if(s[pos].left!=-1)x=s[s[pos].left].val;
      upd(s[pos].right,(l+r)/2+1,r,p,v);
      y=s[s[pos].right].val;
    }
    s[pos].val=__gcd(x,y);
  }
  ll query(int pos,int l,int r,int a,int b){
    if(pos==-1)return 0;
    if(b<l || r<a)return 0;
    if(a<=l && r<=b){
        return s[pos].val;
    }
    return __gcd(query(s[pos].left,l,(l+r)/2,a,b),query(s[pos].right,(l+r)/2+1,r,a,b));
  }
};
class segofseg{
  public:
  struct node{
    int left,right;
    segment k;
    node(){
      left=right=-1;
    }
  };
  vector<node> s=vector<node>(1);
  node def;
  void upd(int pos,int l,int r,int p,int 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(int pos,int l,int r,int a,int b,int x,int y){
    if(pos==-1)return 0;
    if(b<l || r<a)return 0;
    if(a<=l && r<=b){
        return s[pos].k.query(0,0,dim-1,x,y);
    }
    return __gcd(query(s[pos].left,l,(l+r)/2,a,b,x,y),query(s[pos].right,(l+r)/2+1,r,a,b,x,y));
  }
}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 2 ms 384 KB Output is correct
2 Correct 4 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 0 ms 256 KB Output is correct
6 Correct 2 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 488 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 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 961 ms 29756 KB Output is correct
5 Correct 794 ms 33640 KB Output is correct
6 Correct 914 ms 30088 KB Output is correct
7 Correct 1052 ms 30060 KB Output is correct
8 Correct 669 ms 20700 KB Output is correct
9 Correct 924 ms 29868 KB Output is correct
10 Correct 900 ms 29412 KB Output is correct
11 Correct 0 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 2 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 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1446 ms 18896 KB Output is correct
13 Correct 1982 ms 10716 KB Output is correct
14 Correct 668 ms 5736 KB Output is correct
15 Correct 2200 ms 13940 KB Output is correct
16 Correct 769 ms 21116 KB Output is correct
17 Correct 1149 ms 16256 KB Output is correct
18 Correct 1728 ms 21240 KB Output is correct
19 Correct 1671 ms 21624 KB Output is correct
20 Correct 1636 ms 21112 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 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 600 KB Output is correct
10 Correct 1 ms 508 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1018 ms 32748 KB Output is correct
13 Correct 813 ms 33520 KB Output is correct
14 Correct 898 ms 30068 KB Output is correct
15 Correct 926 ms 30180 KB Output is correct
16 Correct 638 ms 20460 KB Output is correct
17 Correct 916 ms 29640 KB Output is correct
18 Correct 868 ms 29160 KB Output is correct
19 Correct 1529 ms 18904 KB Output is correct
20 Correct 1937 ms 10624 KB Output is correct
21 Correct 659 ms 5368 KB Output is correct
22 Correct 2124 ms 13888 KB Output is correct
23 Correct 800 ms 21176 KB Output is correct
24 Correct 1163 ms 16248 KB Output is correct
25 Correct 1739 ms 22396 KB Output is correct
26 Correct 1619 ms 22452 KB Output is correct
27 Correct 1557 ms 21896 KB Output is correct
28 Correct 907 ms 152552 KB Output is correct
29 Correct 1760 ms 169284 KB Output is correct
30 Correct 3321 ms 123868 KB Output is correct
31 Correct 3228 ms 100280 KB Output is correct
32 Correct 581 ms 4856 KB Output is correct
33 Correct 788 ms 7128 KB Output is correct
34 Correct 933 ms 166412 KB Output is correct
35 Correct 1311 ms 86424 KB Output is correct
36 Correct 2235 ms 166756 KB Output is correct
37 Correct 1998 ms 166452 KB Output is correct
38 Correct 1952 ms 166328 KB Output is correct
39 Correct 1733 ms 129104 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 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 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 879 ms 32812 KB Output is correct
13 Correct 727 ms 33388 KB Output is correct
14 Correct 950 ms 29936 KB Output is correct
15 Correct 981 ms 29932 KB Output is correct
16 Correct 644 ms 20684 KB Output is correct
17 Correct 961 ms 29812 KB Output is correct
18 Correct 889 ms 28364 KB Output is correct
19 Correct 1421 ms 17568 KB Output is correct
20 Correct 1936 ms 9272 KB Output is correct
21 Correct 649 ms 4604 KB Output is correct
22 Correct 2241 ms 12428 KB Output is correct
23 Correct 782 ms 19576 KB Output is correct
24 Correct 1152 ms 15368 KB Output is correct
25 Correct 1706 ms 20472 KB Output is correct
26 Correct 1603 ms 20620 KB Output is correct
27 Correct 1473 ms 19960 KB Output is correct
28 Correct 871 ms 152076 KB Output is correct
29 Correct 1660 ms 168560 KB Output is correct
30 Correct 3378 ms 122884 KB Output is correct
31 Correct 3248 ms 99644 KB Output is correct
32 Correct 627 ms 3960 KB Output is correct
33 Correct 767 ms 6264 KB Output is correct
34 Correct 890 ms 165856 KB Output is correct
35 Correct 1250 ms 85660 KB Output is correct
36 Correct 2178 ms 165760 KB Output is correct
37 Correct 1944 ms 165828 KB Output is correct
38 Correct 1928 ms 165368 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 -