oj.uz

Submission #132551

# Submission time Handle Problem Language Result Execution time Memory
132551 2019-07-19T07:13:28 Z Adhyyan1252 Dojave (COCI17_dojave) C++11
112 / 140
 4000 ms 107132 KB 
#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;


struct segtree{
	vector<ii> t;
	vector<int> lazy;
	int sz, M;

	ii merge(ii a, ii b){
		if(a.first > b.first) swap(a, b);
		if(a.second == 0) swap(a, b);
		if(a.first == b.first) return {a.first, a.second + b.second};
		else return a;
	}
	segtree(){}
	segtree(int mod, int size){
		sz = size;
		M = mod;
		t = vector<ii>(size*2);
		lazy = vector<int>(size*2, 0);
		build(1, 0, sz-1);
	}

	void build(int i, int s, int e){
		if(s == e){
			t[i] = {0, ((s%4) == M)?1:0};
			return;
		}
		int m = (s + e)/2;
		build(i*2, s, m); build(i*2+1, m+1, e);
		t[i].second = t[i*2].second + t[i*2+1].second;
	}

	void prop(int i, int s, int e){
		if(s != e){
			lazy[i*2] += lazy[i];
			lazy[i*2+1] += lazy[i];
		}
		t[i].first += lazy[i];
		lazy[i] = 0;
	}

	void upd(int i, int s, int e, int l, int r, int v){
		//cout<<"UDPING "<<i<<" "<<s<<" "<<e<<endl;
		if(l <= s && e <= r){
			lazy[i] += v;
			prop(i, s, e);
			return;
		}
		prop(i, s, e);
		if(s > r || e < l || s > e) return;
		int m = (s + e)/2;
		upd(i*2, s, m, l, r, v); upd(i*2+1, m+1, e, l, r, v);
		t[i] = merge(t[i*2], t[i*2+1]);
	}

	int query(int i, int s, int e, int l, int r){
		//cout<<"QUERY "<<i<<" "<<s<<" "<<e<<endl;
		prop(i, s, e);
		if(l <= s && e <= r) return (t[i].first == 0?t[i].second:0);
		if(s > r || e < l || s > e) return 0;
		int m = (s + e)/2;
		return query(i*2, s, m, l, r) + query(i*2+1, m+1, e, l, r);
	}

	// void print(int i, int s, int e){
	// 	prop(i, s, e);
	// 	//cout<<"S: "<<M<<" "<<i<<" "<<s<<" , "<<e<<" "<<t[i].first<<" "<<t[i].second<<endl;
	// 	if(s == e){
	// 		return;
	// 	}
	// 	int m = (s + e)/2;
	// 	print(i*2, s, m);
	// 	print(i*2+1, m+1, e);
	// }

};




signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int m, n; cin>>m; n = (1<<m);
	int F = n - 1;
	if(m == 1){
		cout<<2<<endl;
		return 0;
	}
	vector<int> a(n), f(n);
	
	for(int i = 0; i < n; i++){
		cin>>a[i];
		f[a[i]] = i;
	}

	vector<segtree> s(4);
	for(int i = 0; i < 4; i++) s[i] = segtree(i, n);
	long long ans = 0;
	//s[0].print(1, 0, n-1);
	for(int i = 0; i < n; i++){
		int next = f[a[i]^F];
		//ans += s[(i+1)%4].query(1, 0, n-1, 0, i-1);
		if(next < i){ //exit
			//cerr<<"EXIT "<<next<<" "<<i<<endl;
			for(int j = 0; j < 4; j++) s[j].upd(1, 0, n-1, 0, next, -1);
			for(int j = 0; j < 4; j++) s[j].upd(1, 0, n-1, next+1, i, 1);
			int temp = s[(i+1)%4].query(1, 0, n-1, 0, i);
			ans += temp;
		}else{ //enter
			
			for(int j = 0; j < 4; j++) s[j].upd(1, 0, n-1, 0, i, 1);
			
		}
		
	}
	// for(int i = 0; i < 4; i++) s[i].print(1, 0, n-1);
	//cout<<"BAD: "<<ans<<endl;
	ans = (1LL*n*(n+1))/2 - ans;
	cout<<ans<<endl;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 888 KB Output is correct
2 Correct 12 ms 760 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1144 KB Output is correct
2 Correct 23 ms 1116 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2040 KB Output is correct
2 Correct 44 ms 2040 KB Output is correct
3 Correct 44 ms 2140 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 7108 KB Output is correct
2 Correct 257 ms 7032 KB Output is correct
3 Correct 439 ms 13816 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 7104 KB Output is correct
2 Correct 505 ms 13800 KB Output is correct
3 Correct 918 ms 27140 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1277 ms 27132 KB Output is correct
2 Correct 1098 ms 27104 KB Output is correct
3 Correct 921 ms 27256 KB Output is correct

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4043 ms 107132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4033 ms 107132 KB Time limit exceeded
2 Halted 0 ms 0 KB -