Submission #484717

#	Time	Username	Problem	Language	Result	Execution time	Memory
484717		kshitij_sodani	Dojave (COCI17_dojave)	C++14	126 / 140	2743 ms	138760 KiB

dojave

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

llo it[1<<20];
llo ind[1<<20];
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define ord tree<llo,null_type,less<llo>,rb_tree_tag,tree_order_statistics_node_update>
vector<llo> re[1<<20];
vector<llo> le[1<<20];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n;
	cin>>n;
	for(llo i=0;i<(1<<n);i++){
		cin>>it[i];
		ind[it[i]]=i;
	}
	if(n==1){
		cout<<3<<endl;
		return 0;
	}
	llo xx2=(1<<n)-1;
	for(llo i=0;i<(1<<n);i++){
		if((ind[i]<ind[i^xx2])){
			//
			re[ind[i^xx2]].pb(ind[i]);
			le[ind[i]].pb(ind[i^xx2]);
			//cout<<ind[i]<<"<"<<ind[i^xx2]<<endl;
		}
	}
	llo ans=((xx2+1)*(xx2+2))/2;
	//cout<<ans<<endl;
	for(llo i=0;i<4;i++){
		//start at mod i
		//end at (i+3)%4
		llo jj=(i+3)%4;
		ord ss;
		multiset<llo> xx;
		for(llo j=(1<<n)-1;j>=0;j--){
			for(auto ii:re[j]){
				xx.insert(j);

			}
			if((j%4)==jj){
				ss.insert(j);
			}
			for(auto ii:le[j]){
				auto kk=xx.find(ii);
				xx.erase(kk);
				while(true){
					auto ac=ss.lower_bound(j);
					if(ac==ss.end()){
						break;
					}

					if((*ac)<ii){
						ss.erase(ac);

					}
					else{
						break;
					}
				}
			}


			if(j%4==i){
				llo ec=(1<<n)+1;
				if(xx.size()){
					ec=*(xx.begin());
				}
				llo cot=ss.order_of_key(ec);
				/*if(cot>0){
					cout<<j<<":"<<cot<<endl;
					for(auto jj:ss){
						cout<<jj<<",";
					}
					cout<<endl;
				}*/
				ans-=cot;
			}

			
		}

	}


	cout<<ans<<endl;





 
	return 0;
}

Compilation message (stderr)

dojave.cpp: In function 'int main()':
dojave.cpp:50:13: warning: unused variable 'ii' [-Wunused-variable]
   50 |    for(auto ii:re[j]){
      |             ^~

• Subtask 1: 0 / 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