oj.uz

Submission #132560

# Submission time Handle Problem Language Result Execution time Memory
132560 2019-07-19T07:24:36 Z Adhyyan1252 Dojave (COCI17_dojave) C++11
140 / 140
 2916 ms 58616 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 || (s%4) == M+1)?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(!lazy[i]) return;
		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){
		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){
		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);
	}
};

signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int m, n; cin>>m; n = (1<<m);
	
	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;
	}

	segtree m0(0, n), m2(2, n);
	long long ans = 0;
	
	for(int i = 0; i < n; i++){
		int next = f[a[i]^(n-1)];
		if(next < i){ //exit
			m0.upd(1, 0, n-1, 0, next, -1);m2.upd(1, 0, n-1, 0, next, -1);
			m0.upd(1, 0, n-1, next+1, i, 1);m2.upd(1, 0, n-1, next+1, i, 1);

			ans += (((i+1)%4 < 2)?m0:m2).query(1, 0, n-1, 0, i);
		}else{ //enter
			m0.upd(1, 0, n-1, 0, i, 1);
			m2.upd(1, 0, n-1, 0, i, 1);
		}
	}
	
	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 380 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 6 ms 504 KB Output is correct
2 Correct 7 ms 504 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1400 KB Output is correct
2 Correct 20 ms 1272 KB Output is correct
3 Correct 20 ms 1272 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 4216 KB Output is correct
2 Correct 99 ms 4216 KB Output is correct
3 Correct 172 ms 7796 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 4216 KB Output is correct
2 Correct 212 ms 7804 KB Output is correct
3 Correct 371 ms 15096 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 15224 KB Output is correct
2 Correct 437 ms 14968 KB Output is correct
3 Correct 371 ms 14968 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2858 ms 58484 KB Output is correct
2 Correct 2413 ms 58500 KB Output is correct
3 Correct 1598 ms 58616 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2916 ms 58512 KB Output is correct
2 Correct 1993 ms 58492 KB Output is correct
3 Correct 1615 ms 58496 KB Output is correct
4 Correct 2571 ms 58432 KB Output is correct