Submission #1208791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208791		pera	Game (IOI13_game)	C++20	0 / 100	1 ms	584 KiB

game

#include "bits/stdc++.h"
#include "game.h"
using namespace std;
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;
}
int N , M;
struct NODE{
   NODE *l , *r;
   long long G = 0;
};
struct node{
   node *l , *r;
   NODE *v;
} *root;

void init(int R, int C) {
   N = R;
   M = C;
}
void upd(NODE *&u , int l , int r , int p , long long x){
   if(!u){
      u = new NODE();
   }
   if(l == r){
      u->G = x;
      return;
   }
   int m = (l + r) / 2;
   if(p <= m){
      upd(u->l , l , m , p , x);
   }else{
      upd(u->r , m + 1 , r , p , x);
   }
   if(!u->l){
      u->l = new NODE();
   }
   if(!u->r){
      u->r = new NODE();
   }
   u->G = gcd2(u->l->G , u->r->G);
};
void update(node* &u , int l , int r , int p , int q , long long x){
   if(l > r){
      return;
   }
   if(!u){
      u = new node();
   }
   upd(u->v , 1 , M , q , x);
   if(l == r){
      return;
   }
   int m = (l + r) / 2;
   if(p <= m){
      update(u->l , l , m , p , q , x);
   }else{
      update(u->r , m + 1 , r , p , q , x);
   }
}
void update(int P, int Q, long long K) {
   ++P , ++Q;
   update(root , 1 , N , P , Q , K);
}
long long query(NODE *&u , int l , int r , int L , int R){
   if(l > r || r < L || l > R || !u){
      return 0LL;
   }
   if(L <= l && r <= R){
      return u->G;
   }
   int m = (l + r) / 2;
   return gcd2(query(u->l , l , m , L , R) , query(u->r , m + 1 , r , L , R));
}
long long query(node*&u , int l , int r , int L , int R, int LL , int RR){
   if(l > r || r < L || l > R || !u){
      return 0LL;
   }
   if(L <= l && r <= R){
      return query(u->v , 1 , M , LL , RR);
   }
   int m = (l + r) / 2;
   return gcd2(query(u->l , l , m , L , R , LL , RR) , query(u->r , m + 1 , r , L , R , LL , RR));
};
long long calculate(int P, int Q, int U, int V) {
   ++P , ++Q , ++U , ++V;
   swap(Q , U);
   return query(root , 1 , N , P , Q , U , V);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20