Submission #258764

#	Time	Username	Problem	Language	Result	Execution time	Memory
258764		davi_bart	Game (IOI13_game)	C++14	37 / 100	13052 ms	8976 KiB

game

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20