oj.uz

Submission #484718

# Submission time Handle Problem Language Result Execution time Memory
484718 2021-11-05T09:30:26 Z kshitij_sodani Dojave (COCI17_dojave) C++14
140 / 140
 2462 ms 131712 KB 
//#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<<2<<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

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49484 KB Output is correct
2 Correct 26 ms 49452 KB Output is correct
3 Correct 29 ms 49488 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 49584 KB Output is correct
2 Correct 26 ms 49612 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49796 KB Output is correct
2 Correct 24 ms 49732 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 49956 KB Output is correct
2 Correct 30 ms 49924 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 50436 KB Output is correct
2 Correct 32 ms 50508 KB Output is correct
3 Correct 31 ms 50508 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 53416 KB Output is correct
2 Correct 97 ms 54696 KB Output is correct
3 Correct 113 ms 56792 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 53300 KB Output is correct
2 Correct 223 ms 59768 KB Output is correct
3 Correct 226 ms 62796 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 64996 KB Output is correct
2 Correct 412 ms 69980 KB Output is correct
3 Correct 225 ms 63524 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2313 ms 111152 KB Output is correct
2 Correct 1306 ms 100092 KB Output is correct
3 Correct 909 ms 115204 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2462 ms 111344 KB Output is correct
2 Correct 1947 ms 131712 KB Output is correct
3 Correct 743 ms 107744 KB Output is correct
4 Correct 1457 ms 101060 KB Output is correct