oj.uz

Submission #258774

# Submission time Handle Problem Language Result Execution time Memory
258774 2020-08-06T14:33:07 Z davi_bart Game (IOI13_game) C++14
63 / 100
 2739 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;
    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);
    }
    return s[pos].val=gcd2(upd(s[pos].left,l,(l+r)/2,p,v),upd(s[pos].right,(l+r)/2+1,r,p,v));
  }
  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;
    }
    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);
    }
    upd(s[pos].left,l,(l+r)/2,p,q,v);
    upd(s[pos].right,(l+r)/2+1,r,p,q,v);

    ll x=s[s[pos].left].k.query(0,0,dim-1,q,q);
    ll 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 1 ms 384 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 5 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 3 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 768 KB Output is correct
11 Correct 4 ms 512 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 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 1281 ms 64524 KB Output is correct
5 Correct 1295 ms 64128 KB Output is correct
6 Correct 1222 ms 61924 KB Output is correct
7 Correct 1360 ms 61348 KB Output is correct
8 Correct 860 ms 39652 KB Output is correct
9 Correct 1197 ms 62704 KB Output is correct
10 Correct 1144 ms 61824 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 4 ms 896 KB Output is correct
3 Correct 3 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 3 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 2 ms 768 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1895 ms 31500 KB Output is correct
13 Correct 2438 ms 17088 KB Output is correct
14 Correct 829 ms 6264 KB Output is correct
15 Correct 2673 ms 24820 KB Output is correct
16 Correct 989 ms 42932 KB Output is correct
17 Correct 1599 ms 31092 KB Output is correct
18 Correct 2473 ms 44664 KB Output is correct
19 Correct 2278 ms 44588 KB Output is correct
20 Correct 2198 ms 43584 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 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 384 KB Output is correct
6 Correct 3 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 2 ms 768 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1171 ms 64688 KB Output is correct
13 Correct 1012 ms 64016 KB Output is correct
14 Correct 1161 ms 62144 KB Output is correct
15 Correct 1164 ms 61584 KB Output is correct
16 Correct 765 ms 39996 KB Output is correct
17 Correct 1180 ms 63012 KB Output is correct
18 Correct 1154 ms 61912 KB Output is correct
19 Correct 1971 ms 31608 KB Output is correct
20 Correct 2430 ms 17208 KB Output is correct
21 Correct 829 ms 6524 KB Output is correct
22 Correct 2739 ms 24728 KB Output is correct
23 Correct 1027 ms 42808 KB Output is correct
24 Correct 1639 ms 31024 KB Output is correct
25 Correct 2410 ms 44436 KB Output is correct
26 Correct 2251 ms 44152 KB Output is correct
27 Correct 2170 ms 43732 KB Output is correct
28 Runtime error 695 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 1 ms 256 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 3 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 768 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1202 ms 65312 KB Output is correct
13 Correct 978 ms 65024 KB Output is correct
14 Correct 1172 ms 63028 KB Output is correct
15 Correct 1174 ms 62348 KB Output is correct
16 Correct 784 ms 40580 KB Output is correct
17 Correct 1206 ms 63356 KB Output is correct
18 Correct 1123 ms 62832 KB Output is correct
19 Correct 1856 ms 31992 KB Output is correct
20 Correct 2402 ms 17528 KB Output is correct
21 Correct 805 ms 6392 KB Output is correct
22 Correct 2696 ms 25036 KB Output is correct
23 Correct 985 ms 42996 KB Output is correct
24 Correct 1609 ms 31216 KB Output is correct
25 Correct 2449 ms 44220 KB Output is correct
26 Correct 2358 ms 44492 KB Output is correct
27 Correct 2149 ms 43768 KB Output is correct
28 Runtime error 698 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -