Submission #122404

#	Time	Username	Problem	Language	Result	Execution time	Memory
122404		ekrem	Game (IOI13_game)	C++98	80 / 100	5465 ms	256000 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas+son)/2)
#define mod 1000000007
#define MAXN 20000005
using namespace std;
// #define fail(s, x...) do { \
// 		fprintf(stderr, s "\n", ## x); \
// 		exit(1); \
// 	} while(0)
 
 
typedef long long ll;
 
int n, m, son1, son, sol[MAXN], sag[MAXN], seg[MAXN], sl[MAXN], sg[MAXN];
ll val[MAXN];
 
ll gcd2(ll X, ll Y) {
    if(X == 0 || Y == 0) {
        return X + Y;
    }
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
 
 
int ver(int k){
	if(!k)return 0;
	return (!seg[k])?seg[k] = ++son:seg[k];
}
 
int slver(int k){
	return (!sl[k])?sl[k] = ++son:sl[k];
}
 
int sgver(int k){
	return (!sg[k])?sg[k] = ++son:sg[k];
}
 
int solver(int k){
	return (!sol[k])?sol[k] = ++son1:sol[k];
}
 
int sagver(int k){
	return (!sag[k])?sag[k] = ++son1:sag[k];
}
 
ll qu2(int k, int bas, int son, int x, int y){
	if(!k or bas > y or son < x)
		return 0;
	if(bas >= x and son <= y)
		return val[k];
	return gcd2(qu2(sl[k], bas, orta, x, y), qu2(sg[k], orta + 1, son, x, y));
}
 
ll qu1(int k, int bas, int son, int x, int y, int xx, int yy){
	if(!k or bas > y or son < x)
		return 0;
	if(bas >= x and son <= y)
		return qu2(seg[k], 1, m, xx, yy);
	return gcd2(qu1(sol[k], bas, orta, x, y, xx, yy), qu1(sag[k], orta + 1, son, x, y, xx, yy));
}
 
void up2(int k, int bas, int son, int x, ll z){
	if(bas == son){
		val[k] = z;
		return;
	}
	if(x <= orta){
		if(!sl[k]){
			int kk = slver(k);
			int bbas = bas, sson = orta;
			while(bbas < sson){
				val[kk] = z;
				if(x <= ((bbas+sson)/2))
					kk = slver(kk), sson = ((bbas+sson)/2);
				else
					kk = sgver(kk), bbas = ((bbas+sson)/2) + 1;
			}
			val[kk] = z;
		} else
			up2(slver(k), bas, orta, x, z);
	}
	else{
		if(!sg[k]){
			int kk = sgver(k);
			int bbas = orta + 1, sson = son;
			while(bbas < sson){
				val[kk] = z;
				if(x <= ((bbas+sson)/2))
					kk = slver(kk), sson = ((bbas+sson)/2);
				else
					kk = sgver(kk), bbas = ((bbas+sson)/2) + 1;
			}
			val[kk] = z;
		} else
			up2(sgver(k), orta + 1, son, x, z);
	}
	val[k] = gcd2(val[sl[k]], val[sg[k]]);
}
 
void up1(int k, int bas, int son, int x, int y, ll z){
	if(bas == son){
		up2(ver(k), 1, m, y, z);
		return;
	}
	if(x <= orta)
		up1(solver(k), bas, orta, x, y, z);
	else
		up1(sagver(k), orta + 1, son, x, y, z);
	z = gcd2(qu2(ver(sol[k]), 1, m, y, y), qu2(ver(sag[k]), 1, m, y, y));
	up2(ver(k), 1, m, y, z);
}
 
void init(int R, int C) {
	n = R;m = C;
	son1++;
}
 
void update(int p, int q, ll k) {
  up1(1, 1, n, p + 1, q + 1, k);
}
 
ll calculate(int p, int q, int u, int v) {
  return qu1(1, 1, n, p+1, u+1, q+1, v+1);
}
 
// int main() {
// 	int R, C, N;
//     int P, Q, U, V;
//     long long K;
//     int i, type;
// 	int res;
 
// 	FILE *f = fopen("in.txt", "r");
// 	if (!f)
// 		fail("Failed to open input file.");
 
// 	res = fscanf(f, "%d", &R);
// 	res = fscanf(f, "%d", &C);
// 	res = fscanf(f, "%d", &N);
 
//     init(R, C);
 
// 	for (i = 0; i < N; i++) {
//         res = fscanf(f, "%d", &type);
//         if (type == 1) {
// 		    res = fscanf(f, "%d%d%lld", &P, &Q, &K);
//             update(P, Q, K);
//         } else if (type == 2) {
// 		    res = fscanf(f, "%d%d%d%d", &P, &Q, &U, &V);
//             printf("%lld\n", calculate(P, Q, U, V));
//         } else
// 			fail("Invalid action type in input file.");
// 	}
// 	fclose(f);
 
// 	return 0;
// }

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;
      ^~~
game.cpp:11:1: warning: multi-line comment [-Wcomment]
 // #define fail(s, x...) do { \
 ^

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