oj.uz

Submission #349844

# Submission time Handle Problem Language Result Execution time Memory
349844 2021-01-18T14:03:24 Z amunduzbaev Game (IOI13_game) C++14
63 / 100
 1819 ms 136568 KB 
#include "game.h"

#ifndef EVAL
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}

ll sx, sy;
vector<vector<ll>> tree;

ll gcd2(ll X, ll Y) {
	ll tmp;
	while (X != Y && Y != 0){
		tmp = X, X = Y, Y = tmp % Y;
	}return X;
}

void update_r(ll x, ll y, ll val, ll lx, ll rx, ll ly, ll ry, ll xx, ll yy){
	if(ly == ry){
		if(lx == rx) tree[xx][yy] = (ll)val;
		else tree[xx][yy] = (ll)gcd2(tree[xx*2][yy], tree[xx*2+1][yy]); 
	}else{
		ll m = (ly + ry)>>1;
		if(y <= m) update_r(x, y, val, lx, rx, ly, m, xx, yy*2);
		else update_r(x, y, val, lx, rx, m+1, ry, xx, yy*2+1);
		tree[xx][yy] = (ll)gcd2(tree[xx][yy*2], tree[xx][yy*2+1]);
	}
}

void update_c(ll x, ll y, ll val, ll lx, ll rx, ll xx){
	if(lx != rx){
		ll m = (lx + rx)>>1;
		if(x <= m) update_c(x, y, val, lx, m, xx*2);
		else update_c(x, y, val, m+1, rx, xx*2+1);
	}
	update_r(x, y, val, lx, rx, 1, sy, xx, 1);
}


void update(int P, int Q, ll K) { update_c(++P, ++Q, K, 1, sx, 1); }

ll qqy(ll ly, ll ry, ll xx, ll qly, ll qry, ll yy){
	if(ly > qry || ry < qly) return 0ll;
	if(ly >= qly && ry <= qry) return (ll)tree[xx][yy];
	
	int m = (ly + ry)>>1;
	ll res1 = (ll)qqy(ly, m, xx, qly, qry, yy*2);
	ll res2 = (ll)qqy(m+1, ry, xx, qly, qry, yy*2+1);
	return (ll)gcd2(res1, res2);
}

ll qq(ll lx, ll rx, ll qlx, ll qrx, ll qly, ll qry, ll xx){
	if(lx > qrx || rx < qlx) return 0ll;
	if(lx >= qlx && rx <= qrx) return (ll)qqy(1, sy, xx, qly, qry, 1);
	
	int m = (lx + rx)>>1;
	ll res1 = (ll)qq(lx, m, qlx, qrx, qly, qry, xx*2);
	ll res2 = (ll)qq(m+1, rx, qlx, qrx, qly, qry, xx*2+1);
	
	return (ll)gcd2(res1, res2);
}

void init(int R, int C) {
	sx = 1, sy = 1;
	
	while(sx < R) sx <<= 1;
	while(sy < C) sy <<= 1;
	
	tree.assign(sx*2, vll(sy*2, 0ll));
}

ll calculate(int x, int y, int xx, int yy) { 
	return qq(1, sx, min(x, xx)+1, max(x, xx)+1, min(y, yy)+1, max(y, yy)+1, 1); 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Correct 1 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 692 ms 72936 KB Output is correct
5 Correct 547 ms 73064 KB Output is correct
6 Correct 712 ms 70044 KB Output is correct
7 Correct 705 ms 69784 KB Output is correct
8 Correct 619 ms 70632 KB Output is correct
9 Correct 719 ms 69788 KB Output is correct
10 Correct 664 ms 69548 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Correct 1 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Correct 1031 ms 39940 KB Output is correct
13 Correct 1463 ms 36460 KB Output is correct
14 Correct 929 ms 135148 KB Output is correct
15 Correct 1760 ms 135284 KB Output is correct
16 Correct 408 ms 135280 KB Output is correct
17 Correct 1623 ms 136416 KB Output is correct
18 Correct 1819 ms 136428 KB Output is correct
19 Correct 1777 ms 136568 KB Output is correct
20 Correct 1715 ms 135660 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Correct 1 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Correct 696 ms 73064 KB Output is correct
13 Correct 529 ms 73064 KB Output is correct
14 Correct 712 ms 70132 KB Output is correct
15 Correct 722 ms 69860 KB Output is correct
16 Correct 616 ms 70504 KB Output is correct
17 Correct 780 ms 69864 KB Output is correct
18 Correct 659 ms 69864 KB Output is correct
19 Correct 1046 ms 39976 KB Output is correct
20 Correct 1451 ms 36620 KB Output is correct
21 Correct 918 ms 135020 KB Output is correct
22 Correct 1739 ms 134636 KB Output is correct
23 Correct 413 ms 133612 KB Output is correct
24 Correct 1594 ms 134220 KB Output is correct
25 Correct 1818 ms 134044 KB Output is correct
26 Correct 1790 ms 134508 KB Output is correct
27 Correct 1720 ms 134104 KB Output is correct
28 Runtime error 3 ms 620 KB Execution killed with signal 6 (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 1 ms 364 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Correct 1 ms 876 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Correct 684 ms 70220 KB Output is correct
13 Correct 526 ms 70504 KB Output is correct
14 Correct 700 ms 68204 KB Output is correct
15 Correct 721 ms 68204 KB Output is correct
16 Correct 609 ms 68204 KB Output is correct
17 Correct 731 ms 68204 KB Output is correct
18 Correct 682 ms 68204 KB Output is correct
19 Correct 1029 ms 37388 KB Output is correct
20 Correct 1439 ms 34024 KB Output is correct
21 Correct 908 ms 132588 KB Output is correct
22 Correct 1747 ms 132716 KB Output is correct
23 Correct 405 ms 132588 KB Output is correct
24 Correct 1586 ms 133356 KB Output is correct
25 Correct 1811 ms 132984 KB Output is correct
26 Correct 1766 ms 133156 KB Output is correct
27 Correct 1715 ms 132460 KB Output is correct
28 Runtime error 3 ms 620 KB Execution killed with signal 6 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -