oj.uz

Submission #58528

# Submission time Handle Problem Language Result Execution time Memory
58528 2018-07-18T04:55:55 Z WA_TLE Wall (IOI14_wall) C++14
61 / 100
 925 ms 263168 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[1<<22]={0};
	static int re[1<<22]={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<(1<<21);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 31 ms 504 KB Output is correct
2 Correct 29 ms 740 KB Output is correct
3 Correct 27 ms 752 KB Output is correct
4 Correct 42 ms 1104 KB Output is correct
5 Correct 24 ms 1200 KB Output is correct
6 Correct 24 ms 1336 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1336 KB Output is correct
2 Correct 423 ms 14664 KB Output is correct
3 Correct 310 ms 14664 KB Output is correct
4 Correct 668 ms 30276 KB Output is correct
5 Correct 510 ms 40904 KB Output is correct
6 Correct 387 ms 49648 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 49648 KB Output is correct
2 Correct 25 ms 49648 KB Output is correct
3 Correct 27 ms 49648 KB Output is correct
4 Correct 33 ms 49648 KB Output is correct
5 Correct 41 ms 49648 KB Output is correct
6 Correct 40 ms 49648 KB Output is correct
7 Correct 26 ms 49648 KB Output is correct
8 Correct 606 ms 53116 KB Output is correct
9 Correct 277 ms 53116 KB Output is correct
10 Correct 800 ms 68632 KB Output is correct
11 Correct 480 ms 79260 KB Output is correct
12 Correct 425 ms 87876 KB Output is correct
13 Correct 32 ms 87876 KB Output is correct
14 Correct 552 ms 91172 KB Output is correct
15 Correct 73 ms 91172 KB Output is correct
16 Correct 813 ms 103588 KB Output is correct
17 Correct 560 ms 112800 KB Output is correct
18 Correct 532 ms 121856 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 121856 KB Output is correct
2 Correct 24 ms 121856 KB Output is correct
3 Correct 24 ms 121856 KB Output is correct
4 Correct 35 ms 121856 KB Output is correct
5 Correct 24 ms 121856 KB Output is correct
6 Correct 26 ms 121856 KB Output is correct
7 Correct 19 ms 121856 KB Output is correct
8 Correct 426 ms 125592 KB Output is correct
9 Correct 264 ms 125592 KB Output is correct
10 Correct 733 ms 141068 KB Output is correct
11 Correct 419 ms 147348 KB Output is correct
12 Correct 468 ms 147348 KB Output is correct
13 Correct 19 ms 147348 KB Output is correct
14 Correct 478 ms 147348 KB Output is correct
15 Correct 63 ms 147348 KB Output is correct
16 Correct 925 ms 147348 KB Output is correct
17 Correct 482 ms 147348 KB Output is correct
18 Correct 477 ms 147348 KB Output is correct
19 Correct 840 ms 204144 KB Output is correct
20 Correct 795 ms 204412 KB Output is correct
21 Correct 746 ms 225096 KB Output is correct
22 Correct 757 ms 225332 KB Output is correct
23 Correct 812 ms 235760 KB Output is correct
24 Correct 737 ms 246188 KB Output is correct
25 Correct 732 ms 256584 KB Output is correct
26 Runtime error 732 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
27 Halted 0 ms 0 KB -