oj.uz

Submission #137282

# Submission time Handle Problem Language Result Execution time Memory
137282 2019-07-27T11:45:36 Z TuGSGeReL Game (IOI13_game) C++17
63 / 100
 9714 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key
#define lb lower_bound
#define ub upper_bound

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;

int rr, cc;
unordered_map <int, unordered_map<int, ll> > sgx;
unordered_map <int, int> which;

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;
}

void upd(int node, int l, int r)
{
	if ( l == r )
	{
		which[l] = node;
		return;
	}
	
	int mid = (l + r) >> 1;
	upd(node << 1, l, mid);
	upd((node << 1) + 1, mid + 1, r);
}

void init(int R, int C) {
	rr = R;
	cc = C;
	upd(1, 1, R);
}

void updy(int node, int l, int r, int idx, ll d, int whi)
{
	if ( l == r && r == idx )
	{
		sgx[whi][node] = d;
		
		do{
			whi >>= 1;
			sgx[whi][node] = gcd2(sgx[whi << 1][node], sgx[(whi << 1) + 1][node]);
		}while(whi > 1);
		
		return;
	}
	
	int mid = (l + r) >> 1;
	
	if ( idx <= mid )
		updy(node << 1, l, mid, idx, d, whi);
	
	else
		updy((node << 1) + 1, mid + 1, r, idx, d, whi);
	
	sgx[whi][node] = gcd2(sgx[whi][node << 1], sgx[whi][(node << 1) + 1]);
	
	do{
		whi >>= 1;
		sgx[whi][node] = gcd2(sgx[whi << 1][node], sgx[(whi << 1) + 1][node]);
	}while(whi > 1);
}


ll lqu(int node, int l, int r, int L, int R, int whi)
{
	if ( l > R || r < L )
		return 0;
		
	if ( l >= L && r <= R )
		return sgx[whi][node];
	
	int mid = (l + r) >> 1;
	
	return gcd2(lqu(node << 1, l, mid, L, R, whi), lqu((node << 1) + 1, mid + 1, r, L, R, whi));
}

ll query (int node, int l, int r, int lx, int ly, int rx, int ry)
{
	if ( l > rx || r < lx )
		return 0;
	
	if ( l >= lx && r <= rx )
		return lqu(1, 1, cc, ly, ry, node);
	
	int mid = (l + r) >> 1;
	
	return gcd2(query(node << 1, l, mid, lx, ly, rx, ry), query((node << 1) + 1, mid + 1, r, lx, ly, rx, ry));
}

void update(int P, int Q, ll K) {
	updy(1, 1, cc, Q + 1, K, which[P + 1]);
}

ll calculate(int P, int Q, int U, int V) {
	return query(1, 1, rr, P + 1, Q + 1, U + 1, V + 1);
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 652 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2982 ms 32968 KB Output is correct
5 Correct 1926 ms 28888 KB Output is correct
6 Correct 3368 ms 72640 KB Output is correct
7 Correct 3407 ms 72428 KB Output is correct
8 Correct 2652 ms 69884 KB Output is correct
9 Correct 3355 ms 73092 KB Output is correct
10 Correct 3113 ms 72280 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 680 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 380 KB Output is correct
12 Correct 4118 ms 36452 KB Output is correct
13 Correct 5039 ms 16896 KB Output is correct
14 Correct 2644 ms 7108 KB Output is correct
15 Correct 6823 ms 23700 KB Output is correct
16 Correct 996 ms 47868 KB Output is correct
17 Correct 8240 ms 175108 KB Output is correct
18 Correct 9194 ms 189812 KB Output is correct
19 Correct 9166 ms 190088 KB Output is correct
20 Correct 9058 ms 189336 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 508 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3132 ms 32904 KB Output is correct
13 Correct 1962 ms 29048 KB Output is correct
14 Correct 3412 ms 72632 KB Output is correct
15 Correct 3235 ms 72296 KB Output is correct
16 Correct 2730 ms 69748 KB Output is correct
17 Correct 3426 ms 73308 KB Output is correct
18 Correct 3292 ms 72276 KB Output is correct
19 Correct 4064 ms 36380 KB Output is correct
20 Correct 5085 ms 16936 KB Output is correct
21 Correct 2650 ms 7208 KB Output is correct
22 Correct 6801 ms 23876 KB Output is correct
23 Correct 1014 ms 47836 KB Output is correct
24 Correct 7906 ms 175052 KB Output is correct
25 Correct 9714 ms 189840 KB Output is correct
26 Correct 9359 ms 189864 KB Output is correct
27 Correct 9397 ms 189284 KB Output is correct
28 Runtime error 801 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3173 ms 33032 KB Output is correct
13 Correct 1928 ms 29052 KB Output is correct
14 Correct 3410 ms 72752 KB Output is correct
15 Correct 3243 ms 72420 KB Output is correct
16 Correct 2765 ms 69816 KB Output is correct
17 Correct 3380 ms 73228 KB Output is correct
18 Correct 3065 ms 72244 KB Output is correct
19 Correct 4249 ms 36416 KB Output is correct
20 Correct 5124 ms 16984 KB Output is correct
21 Correct 2682 ms 7240 KB Output is correct
22 Correct 6809 ms 23736 KB Output is correct
23 Correct 1033 ms 47892 KB Output is correct
24 Correct 8221 ms 175312 KB Output is correct
25 Correct 9653 ms 189952 KB Output is correct
26 Correct 9533 ms 189856 KB Output is correct
27 Correct 9186 ms 189344 KB Output is correct
28 Runtime error 764 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -