oj.uz

Submission #258793

# Submission time Handle Problem Language Result Execution time Memory
258793 2020-08-06T14:50:39 Z davi_bart Game (IOI13_game) C++14
80 / 100
 3540 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(int pos,int l,int r,int a,int 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{
    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(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 2 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 4 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 508 KB Output is correct
11 Correct 2 ms 384 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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 965 ms 30588 KB Output is correct
5 Correct 997 ms 31464 KB Output is correct
6 Correct 1012 ms 27888 KB Output is correct
7 Correct 981 ms 28008 KB Output is correct
8 Correct 640 ms 18568 KB Output is correct
9 Correct 992 ms 27888 KB Output is correct
10 Correct 982 ms 27108 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 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 2 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1581 ms 16348 KB Output is correct
13 Correct 2179 ms 8204 KB Output is correct
14 Correct 767 ms 2928 KB Output is correct
15 Correct 2434 ms 11180 KB Output is correct
16 Correct 935 ms 18512 KB Output is correct
17 Correct 1294 ms 13384 KB Output is correct
18 Correct 1845 ms 18680 KB Output is correct
19 Correct 1799 ms 19028 KB Output is correct
20 Correct 1542 ms 18624 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 384 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 640 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 952 ms 30696 KB Output is correct
13 Correct 803 ms 31456 KB Output is correct
14 Correct 965 ms 27880 KB Output is correct
15 Correct 950 ms 27764 KB Output is correct
16 Correct 654 ms 18260 KB Output is correct
17 Correct 993 ms 27528 KB Output is correct
18 Correct 1156 ms 27148 KB Output is correct
19 Correct 1547 ms 16764 KB Output is correct
20 Correct 2083 ms 8216 KB Output is correct
21 Correct 642 ms 2808 KB Output is correct
22 Correct 2400 ms 11148 KB Output is correct
23 Correct 779 ms 18552 KB Output is correct
24 Correct 1190 ms 13688 KB Output is correct
25 Correct 1799 ms 19448 KB Output is correct
26 Correct 1660 ms 19576 KB Output is correct
27 Correct 1593 ms 18760 KB Output is correct
28 Correct 887 ms 150732 KB Output is correct
29 Correct 1781 ms 167748 KB Output is correct
30 Correct 3421 ms 121704 KB Output is correct
31 Correct 3392 ms 98296 KB Output is correct
32 Correct 577 ms 2808 KB Output is correct
33 Correct 763 ms 5240 KB Output is correct
34 Correct 972 ms 164556 KB Output is correct
35 Correct 1270 ms 84504 KB Output is correct
36 Correct 2251 ms 164600 KB Output is correct
37 Correct 2035 ms 164620 KB Output is correct
38 Correct 1999 ms 164480 KB Output is correct
39 Correct 1645 ms 126968 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 0 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 1 ms 508 KB Output is correct
11 Correct 1 ms 416 KB Output is correct
12 Correct 983 ms 30592 KB Output is correct
13 Correct 830 ms 31208 KB Output is correct
14 Correct 971 ms 27672 KB Output is correct
15 Correct 987 ms 27492 KB Output is correct
16 Correct 648 ms 18412 KB Output is correct
17 Correct 1025 ms 27400 KB Output is correct
18 Correct 918 ms 26860 KB Output is correct
19 Correct 1547 ms 16184 KB Output is correct
20 Correct 2158 ms 8088 KB Output is correct
21 Correct 670 ms 3064 KB Output is correct
22 Correct 2337 ms 10964 KB Output is correct
23 Correct 759 ms 18296 KB Output is correct
24 Correct 1163 ms 13756 KB Output is correct
25 Correct 1776 ms 19240 KB Output is correct
26 Correct 1716 ms 19564 KB Output is correct
27 Correct 1596 ms 18808 KB Output is correct
28 Correct 891 ms 150616 KB Output is correct
29 Correct 1763 ms 167248 KB Output is correct
30 Correct 3540 ms 121328 KB Output is correct
31 Correct 3395 ms 97892 KB Output is correct
32 Correct 584 ms 2424 KB Output is correct
33 Correct 760 ms 4732 KB Output is correct
34 Correct 953 ms 164116 KB Output is correct
35 Correct 1279 ms 84304 KB Output is correct
36 Correct 2376 ms 164352 KB Output is correct
37 Correct 2027 ms 164296 KB Output is correct
38 Correct 1954 ms 163756 KB Output is correct
39 Runtime error 1090 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -