oj.uz

Submission #276901

# Submission time Handle Problem Language Result Execution time Memory
276901 2020-08-20T18:27:58 Z _7_7_ Game (IOI13_game) C++14
63 / 100
 2245 ms 81400 KB 
#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
 
 
typedef pair < long long, long long > pll;    
typedef unsigned long long ull;
typedef pair < int, int > pii;
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;
 
typedef tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
 
const int inf = 1e9, maxn = 2e5 + 48, mod = 998244353, N = 3e5 + 11;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}, block = 300;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = acos(-1);
const ll INF = 1e18;

int Sz;

struct ST {
	int l, r;
	ll g;
};

ST T[N << 3];

void upd1 (int pos, ll x, int v, int tl = 0, int tr = inf - 1) {
	if (tl == tr) {
		T[v].g = x;
		return;
	}

	int tm = (tl + tr) >> 1;
	if (pos <= tm) {
		if (!T[v].l) 
			T[v].l = ++Sz;
		upd1(pos, x, T[v].l, tl, tm);
	} else {
		if (!T[v].r)
			T[v].r = ++Sz;
		upd1(pos, x, T[v].r, tm + 1, tr);
	}

	T[v].g = __gcd(T[T[v].l].g, T[T[v].r].g);
}

ll get1 (int l, int r, int v, int tl = 0, int tr = inf - 1) {
	if (l > r || tl > r || l > tr)
		return 0;

	if (l <= tl && tr <= r)
		return T[v].g;

	int tm = (tl + tr) >> 1;
	
	ll res = 0;
	
	if (T[v].l)
		res = get1(l, r, T[v].l, tl, tm);

	if (T[v].r)
		res = __gcd(res, get1(l, r, T[v].r, tm + 1, tr));

 	return res;
}

ll get2 (int pos, int v, int tl = 0, int tr = inf - 1) {
	if (tl == tr) 
		return T[v].g; 

	int tm = (tl + tr) >> 1;
	if (pos <= tm) {
		if (!T[v].l)
			return 0;
		return get2(pos, T[v].l, tl, tm);
	}

	if (!T[v].r)
		return 0;

	return get2(pos, T[v].r, tm + 1, tr);
}


struct STT {
	int l, r, v;
};

STT TT[N];

int Sz1;



void upd (int x, int y, ll z, int v = 1, int tl = 0, int tr = inf - 1) {
	if (tl == tr) {
		upd1(y, z, TT[v].v);
		return;
	}

	int tm = (tl + tr) >> 1;

	if (x <= tm) {
		if (!TT[v].l) {
			TT[v].l = ++Sz1;
			TT[Sz1].v = ++Sz;
		}
		upd(x, y, z, TT[v].l, tl, tm);
	} else {
		if (!TT[v].r) {
			TT[v].r = ++Sz1;
			TT[Sz1].v = ++Sz;
		}
		upd(x, y, z, TT[v].r, tm + 1, tr);
	}

	ll cur = 0;
	if (TT[v].l) 
		cur = get2(y, TT[TT[v].l].v); 
	
	if (TT[v].r)
		cur = __gcd(cur, get2(y, TT[TT[v].r].v));

	upd1(y, cur, TT[v].v);
}

ll get (int l, int r, int x, int y, int v, int tl = 0, int tr = inf - 1) {
	if (l > r || tl > r || l > tr)
		return 0;

	if (l <= tl && tr <= r)
		return get1(x, y, TT[v].v);

	int tm = (tl + tr) >> 1;	
	
	ll res = 0;
	
	if (TT[v].l)
		res = get(l, r, x, y, TT[v].l, tl, tm);

	if (TT[v].r)
		res = __gcd(res, get(l, r, x, y, TT[v].r, tm + 1, tr));

	return res;
}


void init(int n, int m) {
	TT[++Sz1].v = ++Sz;
}

void update(int x, int y, ll z) {
//	cerr << x << ' ' << y << ' ' << z << endl;
	upd(x, y, z, 1);
}

long long calculate(int lf, int x, int rg, int y) {		
//	cerr << x << ' ' << y << ' ' << lf << ' ' << rg << endl;
    return get(lf, rg, x, y, 1);
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 947 ms 28336 KB Output is correct
5 Correct 785 ms 28604 KB Output is correct
6 Correct 935 ms 25420 KB Output is correct
7 Correct 962 ms 25080 KB Output is correct
8 Correct 661 ms 16544 KB Output is correct
9 Correct 958 ms 25396 KB Output is correct
10 Correct 968 ms 25472 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1441 ms 13248 KB Output is correct
13 Correct 1883 ms 6648 KB Output is correct
14 Correct 637 ms 2576 KB Output is correct
15 Correct 2175 ms 8852 KB Output is correct
16 Correct 630 ms 13688 KB Output is correct
17 Correct 1260 ms 10536 KB Output is correct
18 Correct 2204 ms 14228 KB Output is correct
19 Correct 1814 ms 14312 KB Output is correct
20 Correct 1636 ms 13432 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 924 ms 28668 KB Output is correct
13 Correct 731 ms 28924 KB Output is correct
14 Correct 920 ms 25720 KB Output is correct
15 Correct 1050 ms 25720 KB Output is correct
16 Correct 718 ms 17012 KB Output is correct
17 Correct 933 ms 25760 KB Output is correct
18 Correct 907 ms 25312 KB Output is correct
19 Correct 1431 ms 12916 KB Output is correct
20 Correct 1888 ms 6332 KB Output is correct
21 Correct 645 ms 2408 KB Output is correct
22 Correct 2245 ms 8696 KB Output is correct
23 Correct 629 ms 13560 KB Output is correct
24 Correct 1256 ms 10304 KB Output is correct
25 Correct 2122 ms 13976 KB Output is correct
26 Correct 1868 ms 14120 KB Output is correct
27 Correct 1795 ms 13348 KB Output is correct
28 Runtime error 216 ms 81400 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 911 ms 28272 KB Output is correct
13 Correct 729 ms 28420 KB Output is correct
14 Correct 911 ms 25400 KB Output is correct
15 Correct 950 ms 25148 KB Output is correct
16 Correct 676 ms 16376 KB Output is correct
17 Correct 1066 ms 25404 KB Output is correct
18 Correct 975 ms 24852 KB Output is correct
19 Correct 1386 ms 12664 KB Output is correct
20 Correct 1848 ms 5960 KB Output is correct
21 Correct 635 ms 1944 KB Output is correct
22 Correct 2210 ms 8228 KB Output is correct
23 Correct 684 ms 13088 KB Output is correct
24 Correct 1326 ms 9844 KB Output is correct
25 Correct 1966 ms 13556 KB Output is correct
26 Correct 1735 ms 13568 KB Output is correct
27 Correct 1677 ms 13136 KB Output is correct
28 Runtime error 220 ms 81400 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -