oj.uz

Submission #258764

# Submission time Handle Problem Language Result Execution time Memory
258764 2020-08-06T14:15:55 Z davi_bart Game (IOI13_game) C++14
37 / 100
 13000 ms 8976 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));
    if(ans==1)return ans;
  }
  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 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 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 1016 ms 8704 KB Output is correct
5 Correct 664 ms 8856 KB Output is correct
6 Correct 682 ms 5548 KB Output is correct
7 Correct 732 ms 5024 KB Output is correct
8 Correct 544 ms 4772 KB Output is correct
9 Correct 649 ms 5372 KB Output is correct
10 Correct 341 ms 4964 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 13008 ms 5324 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 572 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 1028 ms 8688 KB Output is correct
13 Correct 663 ms 8728 KB Output is correct
14 Correct 678 ms 5548 KB Output is correct
15 Correct 730 ms 5280 KB Output is correct
16 Correct 533 ms 4944 KB Output is correct
17 Correct 665 ms 5240 KB Output is correct
18 Correct 366 ms 4832 KB Output is correct
19 Execution timed out 13052 ms 5036 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 1014 ms 8976 KB Output is correct
13 Correct 657 ms 8864 KB Output is correct
14 Correct 690 ms 5544 KB Output is correct
15 Correct 762 ms 5148 KB Output is correct
16 Correct 536 ms 4988 KB Output is correct
17 Correct 649 ms 5332 KB Output is correct
18 Correct 344 ms 4856 KB Output is correct
19 Execution timed out 13044 ms 5304 KB Time limit exceeded
20 Halted 0 ms 0 KB -