Submission #132546

#	Time	Username	Problem	Language	Result	Execution time	Memory
132546		Adhyyan1252	Dojave (COCI17_dojave)	C++11	70 / 140	4045 ms	112388 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)?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;
		prop(i, s, e);
		if(l <= s && e <= r){
			lazy[i] += v;
			prop(i, s, e);
			return;
		}
		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);
			//cout<<"ADDING "<<i<<" "<<temp<<endl;
			ans += temp;
		}else{ //enter
			//cerr<<"ENTER "<<i<<" "<<next<<endl;
			for(int j = 0; j < 4; j++) s[j].upd(1, 0, n-1, 0, i, 1);
			// cout<<"AFTER UPD: "<<s[0].lazy[9]<<endl;
			//ans += s[(i+1)%4].query(1, 0, n-1, 0, i);
		}
		s[0].print(1, 0, n-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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14