Submission #281845

#	Time	Username	Problem	Language	Result	Execution time	Memory
281845		shayan_p	Game (IOI13_game)	C++14	80 / 100	4668 ms	256000 KiB

game

// And you curse yourself for things you never done
 
#include<bits/stdc++.h>
#include "game.h"
 
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;

const int MAX = (3e5) * 70;

int N, M;

int L[MAX];
ll g[MAX];
int C;

inline int NEW(){
    C+= 2;
    assert(C < MAX);
    return C-1;
}
void _put(int id, int pos, ll x, int l = 0, int r = M){
    if(r-l == 1){
	g[id] = x;
	return;
    }
    int mid = (l+r) >> 1;
    if(!L[id])
	L[id] = NEW();
    if(pos < mid){
	_put(L[id], pos, x, l, mid);
    }
    else{
	_put(L[id] ^ 1, pos, x, mid, r);
    }
    g[id] = __gcd(L[id] ? g[L[id]] : 0, L[id] ? g[L[id] ^ 1] : 0);
}
ll _ask(int id, int f, int s, int l = 0, int r = M){
    if(r <= f || s <= l)
	return 0;
    if(f <= l && r <= s)
	return g[id];
    int mid = (l+r) >> 1;
    return __gcd(L[id] ? _ask(L[id], f, s, l, mid) : 0, L[id] ? _ask(L[id] ^ 1, f, s, mid, r) : 0);
}
struct node2{
    int g = 0;
    node2 *L = 0, *R = 0;
    void put(int posx, int posy, ll x, int l = 0, int r = N){
	ll num = x;
	if(r-l > 1){
	    int mid = (l+r) >> 1;
	    if(posx < mid){
		if(!L)
		    L = new node2();
		L->put(posx, posy, x, l, mid);
	    }
	    else{
		if(!R)
		    R = new node2();
		R->put(posx, posy, x, mid, r);
	    }
	    num = __gcd(L ? _ask(L->g, posy, posy+1) : 0, R ? _ask(R->g, posy, posy+1) : 0);
	}
	if(!g)
	    g = NEW();
	_put(g, posy, num);
    }
    ll ask(int f, int s, int ff, int ss, int l = 0, int r = N){
	if(r <= f || s <= l)
	    return 0;
	if(f <= l && r <= s)
	    return g ? _ask(g, ff, ss) : 0;
	int mid = (l+r) >> 1;
	return __gcd(L ? L->ask(f, s, ff, ss, l, mid) : 0, R ? R->ask(f, s, ff, ss, mid, r) : 0);
    }
};
 
node2* root;
 
void init(int N, int M){
    ::N = N, ::M = M;
    root = new node2();
}
void update(int x, int y, ll w){
    root->put(x, y, w);
}
ll calculate(int x, int y, int xx, int yy){
    return root->ask(x, ++xx, y, ++yy);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~

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