oj.uz

Submission #258763

# Submission time Handle Problem Language Result Execution time Memory
258763 2020-08-06T14:12:33 Z davi_bart Game (IOI13_game) C++14
37 / 100
 13000 ms 12772 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);
  }
};
segment seg[2500];
void init(int R, int C) {
}

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

long long calculate(int P, int Q, int U, int V) {
  ll ans=0;
  for(ll i=P;i<=U;i++){
    ans=gcd2(ans,seg[i].query(0,0,dim-1,Q,V));
  }
  return ans;
}

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 512 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 994 ms 12652 KB Output is correct
5 Correct 646 ms 12184 KB Output is correct
6 Correct 684 ms 9968 KB Output is correct
7 Correct 750 ms 9500 KB Output is correct
8 Correct 541 ms 8568 KB Output is correct
9 Correct 738 ms 9552 KB Output is correct
10 Correct 678 ms 9188 KB Output is correct
11 Correct 1 ms 512 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Execution timed out 13094 ms 6136 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1031 ms 12548 KB Output is correct
13 Correct 643 ms 12436 KB Output is correct
14 Correct 719 ms 9824 KB Output is correct
15 Correct 803 ms 9376 KB Output is correct
16 Correct 547 ms 8696 KB Output is correct
17 Correct 747 ms 9556 KB Output is correct
18 Correct 678 ms 9184 KB Output is correct
19 Execution timed out 13008 ms 6180 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1066 ms 12772 KB Output is correct
13 Correct 627 ms 12332 KB Output is correct
14 Correct 681 ms 9928 KB Output is correct
15 Correct 807 ms 9372 KB Output is correct
16 Correct 525 ms 8568 KB Output is correct
17 Correct 742 ms 9432 KB Output is correct
18 Correct 651 ms 9072 KB Output is correct
19 Execution timed out 13050 ms 6216 KB Time limit exceeded
20 Halted 0 ms 0 KB -