oj.uz

Submission #58530

# Submission time Handle Problem Language Result Execution time Memory
58530 2018-07-18T05:02:01 Z WA_TLE Wall (IOI14_wall) C++14
100 / 100
 906 ms 76964 KB 
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
//#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1e9+7;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
//llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
/*
ioi2014 day1 prob2 wall

*/
#include<wall.h>
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
	static int ad[4097200]={0};
	static int re[4097200]={0};
	//当然のようにセグメントツリーを行う
	//seg木は番兵のため1～nで行う　ごめんね
	for(int h=0;h<k;h++){
		int hi=left[h]+1;
		int mg=right[h]+1;
		int ta=height[h];
		
		int biL=1;
		for(int j=20;j>=0;j--){
			maxeq(ad[biL+biL],ad[biL]);
			maxeq(ad[biL+biL+1],ad[biL]);
			maxeq(re[biL+biL],ad[biL]);
			maxeq(re[biL+biL+1],ad[biL]);
			mineq(re[biL+biL],re[biL]);
			mineq(re[biL+biL+1],re[biL]);
			mineq(ad[biL+biL],re[biL]);
			mineq(ad[biL+biL+1],re[biL]);
			ad[biL]=0;
			re[biL]=mod;
			biL*=2;
			if((hi-1)&(1<<j)){biL++;}
		}
		int biR=1;
		for(int j=20;j>=0;j--){
			maxeq(ad[biR+biR],ad[biR]);
			maxeq(ad[biR+biR+1],ad[biR]);
			maxeq(re[biR+biR],ad[biR]);
			maxeq(re[biR+biR+1],ad[biR]);
			mineq(re[biR+biR],re[biR]);
			mineq(re[biR+biR+1],re[biR]);
			mineq(ad[biR+biR],re[biR]);
			mineq(ad[biR+biR+1],re[biR]);
			ad[biR]=0;
			re[biR]=mod;
			biR*=2;
			if((mg+1)&(1<<j)){biR++;}
		}
		if(op[h]==1){//add
			while(biL+1<biR){
				if(biL%2==0){maxeq(ad[biL+1],ta);maxeq(re[biL+1],ta);}
				if(biR%2==1){maxeq(ad[biR-1],ta);maxeq(re[biR-1],ta);}
				biL/=2;biR/=2;
			}
		}else{//rem
			while(biL+1<biR){
				if(biL%2==0){mineq(re[biL+1],ta);mineq(ad[biL+1],ta);}
				if(biR%2==1){mineq(re[biR-1],ta);mineq(ad[biR-1],ta);}
				biL/=2;biR/=2;
			}
		}
	}
	//最後にセグ木の伝搬をする
	for(int i=1;i<2048590;i++){
		maxeq(ad[i+i],ad[i]);
		maxeq(ad[i+i+1],ad[i]);
		maxeq(re[i+i],ad[i]);
		maxeq(re[i+i+1],ad[i]);
		mineq(re[i+i],re[i]);
		mineq(re[i+i+1],re[i]);
		mineq(ad[i+i],re[i]);
		mineq(ad[i+i+1],re[i]);
	}
	for(int i=0;i<n;i++){finalHeight[i]=ad[i+1+(1<<21)];}
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 504 KB Output is correct
2 Correct 25 ms 612 KB Output is correct
3 Correct 20 ms 836 KB Output is correct
4 Correct 41 ms 1180 KB Output is correct
5 Correct 27 ms 1392 KB Output is correct
6 Correct 25 ms 1496 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1496 KB Output is correct
2 Correct 380 ms 14828 KB Output is correct
3 Correct 323 ms 14828 KB Output is correct
4 Correct 892 ms 24960 KB Output is correct
5 Correct 460 ms 25312 KB Output is correct
6 Correct 460 ms 25456 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 25456 KB Output is correct
2 Correct 22 ms 25456 KB Output is correct
3 Correct 31 ms 25456 KB Output is correct
4 Correct 41 ms 25456 KB Output is correct
5 Correct 32 ms 25456 KB Output is correct
6 Correct 24 ms 25456 KB Output is correct
7 Correct 21 ms 25456 KB Output is correct
8 Correct 440 ms 25456 KB Output is correct
9 Correct 353 ms 25456 KB Output is correct
10 Correct 789 ms 25456 KB Output is correct
11 Correct 466 ms 25456 KB Output is correct
12 Correct 427 ms 25604 KB Output is correct
13 Correct 20 ms 25604 KB Output is correct
14 Correct 373 ms 25604 KB Output is correct
15 Correct 58 ms 25604 KB Output is correct
16 Correct 856 ms 25604 KB Output is correct
17 Correct 470 ms 25604 KB Output is correct
18 Correct 495 ms 25604 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 25604 KB Output is correct
2 Correct 27 ms 25604 KB Output is correct
3 Correct 23 ms 25604 KB Output is correct
4 Correct 29 ms 25604 KB Output is correct
5 Correct 29 ms 25604 KB Output is correct
6 Correct 28 ms 25604 KB Output is correct
7 Correct 25 ms 25604 KB Output is correct
8 Correct 413 ms 25604 KB Output is correct
9 Correct 300 ms 25604 KB Output is correct
10 Correct 831 ms 25604 KB Output is correct
11 Correct 420 ms 25604 KB Output is correct
12 Correct 444 ms 25604 KB Output is correct
13 Correct 24 ms 25604 KB Output is correct
14 Correct 430 ms 25604 KB Output is correct
15 Correct 62 ms 25604 KB Output is correct
16 Correct 873 ms 25604 KB Output is correct
17 Correct 521 ms 25604 KB Output is correct
18 Correct 445 ms 25604 KB Output is correct
19 Correct 906 ms 71844 KB Output is correct
20 Correct 877 ms 71844 KB Output is correct
21 Correct 832 ms 71976 KB Output is correct
22 Correct 733 ms 71976 KB Output is correct
23 Correct 671 ms 71976 KB Output is correct
24 Correct 774 ms 71976 KB Output is correct
25 Correct 700 ms 71976 KB Output is correct
26 Correct 786 ms 71976 KB Output is correct
27 Correct 809 ms 76964 KB Output is correct
28 Correct 844 ms 76964 KB Output is correct
29 Correct 849 ms 76964 KB Output is correct
30 Correct 873 ms 76964 KB Output is correct