oj.uz

답안 #399496

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
399496 2021-05-05T23:05:52 Z cfalas 게임 (IOI13_game) C++14
37 / 100
 13000 ms 226080 KB 
#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)

int t, n;
vi a, b;

static int M;
//static map<int, map<ii, int> > mapper;

long long gcd(long long X, long long Y) {
	//return X + Y;
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}


template<typename Q>
struct seg_tree_2d{

	template<typename T>
	struct seg_tree{
		struct node{
			T val;
			node* left=nullptr;
			node* right=nullptr;
			node() {val=0;}
			node(T v) {val=v;}
		};
		node* root=nullptr;
		T RAND_VALUE=0;
		seg_tree(){root = new node();}

		unordered_map<int, T> leaves;
		inline void merge(node *par){
			par->val = gcd(par->left->val , par->right->val);
		}

		inline void update_node(node* ind, T val, int l, int r){
			//cout<<"Updating "<<l<<" "<<r<<endl;
			leaves[l] = val;
			if(val==0) leaves.erase(l);
			ind->val = val;
		}

		inline void create_children(node* ind){
			if(ind->left==nullptr) ind->left= new node();
			if(ind->right==nullptr) ind->right = new node();
		}

		void print(node* ind, int l=0, int r=M-1){
			cout<<"("<<l<<" "<<r<<": "<<ind->val<<") ";
			if(ind->left!=nullptr) print(ind->left, l, MID);
			if(ind->right!=nullptr) print(ind->right, MID+1, r);
		}

		void build(node* ind, vector<T>& arr, int l=0, int r=M-1){
			if(l==r) ind->val = node(arr[l]);
			else{
				create_children(ind);
				build(ind->left, arr,l,MID);
				build(ind->right, arr,MID+1,r);

				merge(ind);
			}
		}

		void update(node* ind, int x, T val, int l=0, int r=M-1){
			if(x==l && r==x) update_node(ind, val,l,r);
			else if(x<l || r<x) return;
			else{
				create_children(ind);
				update(ind->left, x,val,l,MID);
				update(ind->right, x,val,MID+1,r);
				merge(ind);
			}
		}

		T query(node* ind, int rl, int rr, int l=0, int r=M-1){
			if(rl<=l && r<=rr) return ind->val;
			else if(rl>r || l>rr) return RAND_VALUE;
			else{
				create_children(ind);
				return  gcd(query(ind->left, rl, rr, l, MID) , query(ind->right, rl,rr,MID+1,r));
			}
		}


	};
	struct node{
		seg_tree<Q>* val = new seg_tree<Q>;
		int left=-1;
		int right=-1;
		node() {left=-1, right=-1;}
	};
	vector<node> seg2d;
	static inline int N;
	Q RAND_VALUE_2d=0;
	seg_tree_2d(int n){N=n, seg2d.assign(1, node());}

	inline void merge(node &par, node &a, node &b, int ind){
		/*
		cout<<"Merging "<<seg2d[ind].left<<" "<<seg2d[ind].right<<endl;
		cout<<&a<<" "<<&b<<" "<<&par<<endl;
		a.val->print();
		cout<<endl;
		b.val->print();
		cout<<endl;
		par.val->print();
		cout<<endl;
		cout<<"LEAVES A: ";
		FOA(v, a.val->leaves) cout<<"("<<v.F<<" "<<v.S<<") ";
		cout<<endl;
		cout<<"LEAVES B: ";
		FOA(v, b.val->leaves) cout<<"("<<v.F<<" "<<v.S<<") ";
		cout<<endl;
		*/
		FOA(v,a.val->leaves){
			Q val = v.S;
			if(b.val->leaves[v.F]) val = gcd(val, b.val->leaves[v.F]);
			if(par.val->leaves[v.F]!=val) par.val->update(par.val->root, v.F, val);
		}
		FOA(v,b.val->leaves){
			Q val = v.S;
			if(a.val->leaves[v.F]) val = gcd(val, a.val->leaves[v.F]);
			if(par.val->leaves[v.F]!=val) par.val->update(par.val->root, v.F, val);
		}
		/*
		cout<<"LEAVES combo: ";
		FOA(v, par.val->leaves) cout<<"("<<v.F<<" "<<v.S<<") ";
		cout<<endl;
		*/
	}

	void print(int l=0, int r=N-1, int ind=0){
		cout<<"L R "<<l<<" "<<r<<" "<<ind<<endl;
		//seg2d[ind].val->print();
		cout<<endl;
		if(seg2d[ind].left!=-1) print(l, MID, seg2d[ind].left);
		if(seg2d[ind].right!=-1) print(MID+1, r, seg2d[ind].right);
	}

	inline void create_children(int ind){
		if(seg2d[ind].left==-1){
			seg2d[ind].left=seg2d.size();
			seg2d.push_back(node());
		}
		if(seg2d[ind].right==-1){
			seg2d[ind].right=seg2d.size();
			seg2d.push_back(node());
		}
	}

	/*
	void build(vector<vector<Q> >& arr, int l=0, int r=N-1, int ind=0){
		if(l==r){
			seg2d[ind].val.build(arr[l]);
		}
		else{
			create_children(ind);
			build(arr,l,MID,seg2d[ind].left);
			build(arr,MID+1,r,seg2d[ind].right);

			merge(seg2d[ind], seg2d[seg2d[ind].left], seg2d[seg2d[ind].right], ind);
		}
	}
	*/

	void update(int y, int x, Q val, int l=0, int r=N-1, int ind=0){
		//cout<<ind<<" ";
		//seg2d[ind].val->print();
		//cout<<endl;
		//if(y==l && y==r) cout<<"Calling update "<<l<<" "<<r<<endl;
		if(y==l && y==r) seg2d[ind].val->update(seg2d[ind].val->root, x, val);
		else if(y<l || r<y) return;
		else{
			create_children(ind);
			update(y,x,val,l,MID,seg2d[ind].left);
			update(y,x,val,MID+1,r,seg2d[ind].right);
			merge(seg2d[ind], seg2d[seg2d[ind].left], seg2d[seg2d[ind].right], ind);
		}
		//cout<<ind<<" ";
		//seg2d[ind].val->print();
		//cout<<endl;
	}

	Q query(int rl, int rr, int xl, int xr, int l=0, int r=N-1, int ind=0){
		if(rl<=l && r<=rr) return seg2d[ind].val->query(seg2d[ind].val->root, xl, xr);
		else if(rl>r || l>rr) return RAND_VALUE_2d;
		else{
			create_children(ind);
			return gcd(query(rl, rr, xl, xr, l, MID, seg2d[ind].left), query(rl,rr,xl, xr, MID+1,r,seg2d[ind].right));
		}
	}

};

seg_tree_2d<ll> seg(n);

void init(int R, int C) {
	M = R;
	seg.N = C;
}

void update(int P, int Q, long long K) {
	//changed.clear();
	seg.update(Q,P,K);
	//seg.print();
	/*
	FOR(i,M){
		FOR(j,M) seg.query(i,i,j,j);
		//FOR(j,M) cout<<setw(1)<<seg.query(i,i,j,j);
		//cout<<endl;
	}
	*/
	//cout<<endl;
}

long long calculate(int P, int Q, int U, int V) {
    return seg.query(Q,V,P,U);
}

/*
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int q;
	cin>>n>>q;
	init(n,n);
	string s[n];
	vector<vector<ll> > a(n, vi(n, 0));
	FOR(i,n) cin>>s[i];

	FOR(i,n) FOR(j,n){
		if(s[i][j]=='*') a[i][j] = 1;
		else a[i][j] = 0;
	}
	seg.build(a);
	while(q--){
		cin>>t;
		if(t==1){
			int x, y;
			cin>>x>>y;
			update(x-1,y-1, 1);
		}
		else{
			int x1, y1, x2, y2;
			cin>>x1>>y1>>x2>>y2;
			cout<<seg.query(x1-1,x2-1, y1-1, y2-1)<<"\n";
		}
	}
}
*/

Compilation message

game.cpp:121:9: warning: inline variables are only available with '-std=c++17' or '-std=gnu++17'
  121 |  static inline int N;
      |         ^~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 548 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 252 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1022 ms 45312 KB Output is correct
5 Correct 737 ms 35760 KB Output is correct
6 Correct 1556 ms 110160 KB Output is correct
7 Correct 1572 ms 109776 KB Output is correct
8 Correct 1306 ms 110512 KB Output is correct
9 Correct 1556 ms 112292 KB Output is correct
10 Correct 1483 ms 109416 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 5315 ms 32324 KB Output is correct
13 Correct 4731 ms 15256 KB Output is correct
14 Correct 860 ms 5760 KB Output is correct
15 Correct 7367 ms 21052 KB Output is correct
16 Correct 9637 ms 40712 KB Output is correct
17 Correct 5168 ms 214596 KB Output is correct
18 Correct 11360 ms 225996 KB Output is correct
19 Correct 11532 ms 226080 KB Output is correct
20 Execution timed out 13048 ms 224268 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1016 ms 43324 KB Output is correct
13 Correct 742 ms 33672 KB Output is correct
14 Correct 1569 ms 108264 KB Output is correct
15 Correct 1587 ms 107976 KB Output is correct
16 Correct 1292 ms 108836 KB Output is correct
17 Correct 1550 ms 110656 KB Output is correct
18 Correct 1469 ms 107688 KB Output is correct
19 Correct 5303 ms 30068 KB Output is correct
20 Correct 4634 ms 13020 KB Output is correct
21 Correct 857 ms 3264 KB Output is correct
22 Correct 7293 ms 18528 KB Output is correct
23 Correct 9489 ms 38384 KB Output is correct
24 Correct 5218 ms 212896 KB Output is correct
25 Correct 11463 ms 224344 KB Output is correct
26 Correct 11802 ms 224340 KB Output is correct
27 Execution timed out 13079 ms 219300 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1020 ms 41784 KB Output is correct
13 Correct 738 ms 32528 KB Output is correct
14 Correct 1530 ms 107296 KB Output is correct
15 Correct 1585 ms 107016 KB Output is correct
16 Correct 1305 ms 107692 KB Output is correct
17 Correct 1559 ms 109492 KB Output is correct
18 Correct 1465 ms 106600 KB Output is correct
19 Correct 5300 ms 28948 KB Output is correct
20 Correct 4683 ms 11872 KB Output is correct
21 Correct 864 ms 2140 KB Output is correct
22 Correct 7297 ms 17284 KB Output is correct
23 Correct 9556 ms 37104 KB Output is correct
24 Correct 5073 ms 211676 KB Output is correct
25 Correct 11414 ms 223112 KB Output is correct
26 Correct 11635 ms 223220 KB Output is correct
27 Execution timed out 13021 ms 217980 KB Time limit exceeded
28 Halted 0 ms 0 KB -