Submission #132560

#	Time	Username	Problem	Language	Result	Execution time	Memory
132560		Adhyyan1252	Dojave (COCI17_dojave)	C++11	140 / 140	2916 ms	58616 KiB

dojave

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14