oj.uz

Submission #1012962

# Submission time Handle Problem Language Result Execution time Memory
1012962 2024-07-03T03:02:25 Z pcc Game (IOI13_game) C++17
63 / 100
 809 ms 121628 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

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

int R,C;
const int mxn = 3e4+10;

struct SEG2D{
	struct node{
		ll val;
		int pl,pr;
		node(){
			val = pl = pr = 0;
		}
	};
	struct node2d{
		int val;
		int pl,pr;
		node2d(){
			val = pl = pr = 0;
		}
	};
	node seg[mxn*10*10];
	node2d seg2[mxn*30];
	int ptr = 0,ptr2 = 0;
	SEG2D(){}
	int newnode(){
		ptr++;
		assert(ptr<mxn*30*30);
		return ptr;
	}
	int newnode2(){
		ptr2++;
		assert(ptr2<mxn*30);
		return ptr2;
	}
	int modify(int now,int l,int r,int p,ll v,int pul,int pur){
		if(!now)now = newnode();
		if(l == r){
			if(v >= 0)seg[now].val = v;
			else seg[now].val = gcd2(seg[pul].val,seg[pur].val);
			return now;
		}
		int mid = (l+r)>>1;
		if(mid>=p)seg[now].pl = modify(seg[now].pl,l,mid,p,v,seg[pul].pl,seg[pur].pl);
		else seg[now].pr = modify(seg[now].pr,mid+1,r,p,v,seg[pul].pr,seg[pur].pr);
		int ls = seg[now].pl,rs = seg[now].pr;
		seg[now].val = gcd2(seg[ls].val,seg[rs].val);
		return now;
	}
	ll getval(int now,int l,int r,int s,int e){
		if(!now)return 0ll;
		if(l>=s&&e>=r)return seg[now].val;
		int mid = (l+r)>>1;
		if(mid>=e)return getval(seg[now].pl,l,mid,s,e);
		else if(mid<s)return getval(seg[now].pr,mid+1,r,s,e);
		else return gcd2(getval(seg[now].pl,l,mid,s,e),getval(seg[now].pr,mid+1,r,s,e));
	}
	int modify2(int now,int l,int r,int row,int col,ll v){
		if(!now)now = newnode2();
		if(l == r){
			seg2[now].val = modify(seg2[now].val,0,C,col,v,0,0);
			//cerr<<"SEG2D:"<<' '<<l<<' '<<r<<' '<<seg[seg2[now].val].val<<endl;
			return now;
		}
		int mid = (l+r)>>1;
		if(mid>=row)seg2[now].pl = modify2(seg2[now].pl,l,mid,row,col,v);
		else seg2[now].pr = modify2(seg2[now].pr,mid+1,r,row,col,v);
		seg2[now].val = modify(seg2[now].val,0,C,col,-1,seg2[seg2[now].pl].val,seg2[seg2[now].pr].val);
		//cerr<<"SEG2D:"<<' '<<l<<' '<<r<<' '<<seg[seg2[now].val].val<<endl;
		return now;
	}
	ll getval2(int now,int l,int r,int sr,int sc,int er,int ec){
		if(!now)return 0ll;
		if(l>=sr&&er>=r){
			//cerr<<"GETVAL: "<<l<<' '<<r<<' '<<getval(seg2[now].val,0,C,sc,ec)<<endl;
			return getval(seg2[now].val,0,C,sc,ec);
		}
		int mid = (l+r)>>1;
		if(mid>=er)return getval2(seg2[now].pl,l,mid,sr,sc,er,ec);
		else if(mid<sr)return getval2(seg2[now].pr,mid+1,r,sr,sc,er,ec);
		else return gcd2(getval2(seg2[now].pl,l,mid,sr,sc,er,ec),getval2(seg2[now].pr,mid+1,r,sr,sc,er,ec));
	}
};

SEG2D seg;
int rt;

void init(int RR, int CC) {
	R = RR,C = CC;
	//cerr<<"INIT!"<<" "<<R<<' '<<C<<endl;
	rt = seg.newnode2();
	//cerr<<"INIT!"<<endl;
}

void update(int P, int Q, long long K) {
	//cerr<<"UPDATE: "<<P<<' '<<Q<<' '<<K<<endl;
	rt = seg.modify2(rt,0,R,P,Q,K);
	//cerr<<"UPDATE DONE!"<<endl;
}

long long calculate(int P, int Q, int U, int V) {
	//cerr<<"CALC: "<<P<<' '<<Q<<' '<<U<<' '<<V<<endl;
	return seg.getval2(rt,0,R,P,Q,U,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 57936 KB Output is correct
2 Correct 19 ms 57948 KB Output is correct
3 Correct 19 ms 57976 KB Output is correct
4 Correct 20 ms 57948 KB Output is correct
5 Correct 20 ms 57948 KB Output is correct
6 Correct 20 ms 57948 KB Output is correct
7 Correct 20 ms 57944 KB Output is correct
8 Correct 23 ms 57944 KB Output is correct
9 Correct 21 ms 57948 KB Output is correct
10 Correct 19 ms 57752 KB Output is correct
11 Correct 19 ms 57948 KB Output is correct
12 Correct 19 ms 57808 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 57944 KB Output is correct
2 Correct 19 ms 57944 KB Output is correct
3 Correct 20 ms 57988 KB Output is correct
4 Correct 260 ms 66372 KB Output is correct
5 Correct 196 ms 66108 KB Output is correct
6 Correct 256 ms 63576 KB Output is correct
7 Correct 257 ms 63420 KB Output is correct
8 Correct 196 ms 63832 KB Output is correct
9 Correct 281 ms 63316 KB Output is correct
10 Correct 229 ms 63020 KB Output is correct
11 Correct 19 ms 57948 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 57944 KB Output is correct
2 Correct 19 ms 57948 KB Output is correct
3 Correct 19 ms 57944 KB Output is correct
4 Correct 19 ms 57948 KB Output is correct
5 Correct 21 ms 57948 KB Output is correct
6 Correct 19 ms 57944 KB Output is correct
7 Correct 20 ms 57948 KB Output is correct
8 Correct 26 ms 57948 KB Output is correct
9 Correct 20 ms 57948 KB Output is correct
10 Correct 17 ms 57928 KB Output is correct
11 Correct 24 ms 58204 KB Output is correct
12 Correct 406 ms 65976 KB Output is correct
13 Correct 717 ms 62548 KB Output is correct
14 Correct 164 ms 62968 KB Output is correct
15 Correct 807 ms 63076 KB Output is correct
16 Correct 294 ms 62804 KB Output is correct
17 Correct 387 ms 64080 KB Output is correct
18 Correct 549 ms 64240 KB Output is correct
19 Correct 493 ms 64372 KB Output is correct
20 Correct 462 ms 63876 KB Output is correct
21 Correct 18 ms 57948 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 57944 KB Output is correct
2 Correct 24 ms 57936 KB Output is correct
3 Correct 18 ms 57944 KB Output is correct
4 Correct 17 ms 57812 KB Output is correct
5 Correct 17 ms 57948 KB Output is correct
6 Correct 17 ms 57984 KB Output is correct
7 Correct 20 ms 57948 KB Output is correct
8 Correct 19 ms 57948 KB Output is correct
9 Correct 19 ms 57948 KB Output is correct
10 Correct 19 ms 57944 KB Output is correct
11 Correct 19 ms 57944 KB Output is correct
12 Correct 260 ms 66388 KB Output is correct
13 Correct 222 ms 66228 KB Output is correct
14 Correct 247 ms 63568 KB Output is correct
15 Correct 286 ms 63316 KB Output is correct
16 Correct 193 ms 63824 KB Output is correct
17 Correct 265 ms 63368 KB Output is correct
18 Correct 235 ms 63056 KB Output is correct
19 Correct 413 ms 66132 KB Output is correct
20 Correct 707 ms 62588 KB Output is correct
21 Correct 166 ms 63056 KB Output is correct
22 Correct 809 ms 63116 KB Output is correct
23 Correct 297 ms 62804 KB Output is correct
24 Correct 407 ms 64080 KB Output is correct
25 Correct 574 ms 64336 KB Output is correct
26 Correct 538 ms 64324 KB Output is correct
27 Correct 466 ms 63668 KB Output is correct
28 Runtime error 141 ms 121628 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 18 ms 57920 KB Output is correct
2 Correct 18 ms 57952 KB Output is correct
3 Correct 18 ms 57948 KB Output is correct
4 Correct 19 ms 57948 KB Output is correct
5 Correct 18 ms 57948 KB Output is correct
6 Correct 18 ms 57948 KB Output is correct
7 Correct 19 ms 57888 KB Output is correct
8 Correct 19 ms 57756 KB Output is correct
9 Correct 22 ms 57964 KB Output is correct
10 Correct 22 ms 58200 KB Output is correct
11 Correct 18 ms 57948 KB Output is correct
12 Correct 276 ms 66420 KB Output is correct
13 Correct 208 ms 66132 KB Output is correct
14 Correct 248 ms 63568 KB Output is correct
15 Correct 263 ms 63208 KB Output is correct
16 Correct 203 ms 63824 KB Output is correct
17 Correct 307 ms 63316 KB Output is correct
18 Correct 244 ms 62960 KB Output is correct
19 Correct 419 ms 66132 KB Output is correct
20 Correct 741 ms 62576 KB Output is correct
21 Correct 173 ms 63060 KB Output is correct
22 Correct 796 ms 63056 KB Output is correct
23 Correct 307 ms 62908 KB Output is correct
24 Correct 431 ms 63988 KB Output is correct
25 Correct 584 ms 64340 KB Output is correct
26 Correct 579 ms 64368 KB Output is correct
27 Correct 481 ms 63852 KB Output is correct
28 Runtime error 134 ms 121424 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -