Submission #426105

#	Time	Username	Problem	Language	Result	Execution time	Memory
426105		Bill_00	Game (IOI13_game)	C++14	37 / 100	13109 ms	196252 KiB

game

#include "game.h"
#include <bits/stdc++.h>
typedef long long ll;
const ll value=3000000000;
using namespace std;
ll x,y,k,x_,y_;
unordered_map<ll,ll>t;
long long gcd2(long long X, long long Y) {
    if(Y>X) swap(X,Y);
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
void updateY(ll vx, ll lx, ll rx, ll vy, ll ly, ll ry) {
    if (ly == ry) {
        if (lx == rx){
            t[vx*value+vy] = k;
        }
        else{
            t[vx*value+vy] = gcd2(t[vx*2*value+vy],t[(vx*2+1)*value+vy]);
            // cout << t[vx*2*value+vy] << '\n';
        }
    } else {
        ll my = (ly + ry) / 2;
        if(my>=y) updateY(vx, lx, rx, vy*2, ly, my);
        else updateY(vx, lx, rx, vy*2+1, my+1, ry);
        t[vx*value+vy] = gcd2(t[vx*value+vy*2],t[vx*value+vy*2+1]);
    }
    // cout << t[vx*value+vy] << ' ' << lx << ' ' << rx << ' ' << ly << ' ' << ry << '\n';
}

void updateX(ll vx, ll lx, ll rx) {
    if (lx != rx) {
        ll mx = (lx + rx) / 2;
        if(mx>=x) updateX(vx*2, lx, mx);
       	else updateX(vx*2+1, mx+1, rx);
    }
    updateY(vx, lx, rx, 1, 0, 1000000000);
}
void init(int R, int C) {
    /* ... */
}
void update(int P, int Q, long long K) {
    x=P;
    y=Q;
    k=K;
   	updateX(1,0,1000000000);
}
ll queryY(ll idx,ll L,ll R,ll idy,ll l,ll r) {
    if(r<y || y_<l) return 0;
    if(y<=l && r<=y_){
    	return t[idx*value+idy];	
    } 
    ll m=l+r>>1;
    return gcd2(queryY(idx,L,R,idy*2,l,m),queryY(idx,L,R,idy*2+1,m+1,r));
}

ll queryX(ll id,ll l,ll r) {
   if(r<x || x_<l) return 0;
   if(x<=l && r<=x_) return queryY(id,l,r,1,0,1000000000);
   ll m=l+r>>1;
   return gcd2(queryX(id*2,l,m),queryX(id*2+1,m+1,r));
}
long long calculate(int P, int Q, int U, int V) {
    /* ... */
    x=P;
    y=Q;
    x_=U;
    y_=V;
    return queryX(1,0,1000000000);
}

Compilation message (stderr)

game.cpp: In function 'll queryY(ll, ll, ll, ll, ll, ll)':
game.cpp:58:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     ll m=l+r>>1;
      |          ~^~
game.cpp: In function 'll queryX(ll, ll, ll)':
game.cpp:65:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |    ll m=l+r>>1;
      |         ~^~

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