oj.uz

Submission #172851

# Submission time Handle Problem Language Result Execution time Memory
172851 2020-01-02T16:50:14 Z maximath_1 Wall (IOI14_wall) C++11
0 / 100
 171 ms 9720 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e18;
vector<ll> stmax, stmin, ans;
void down(ll idx, ll mn, ll mx){
	stmin[idx]=min(stmin[idx], mn);
	stmax[idx]=min(stmax[idx], mn);
	stmax[idx]=max(stmax[idx], mx);
} 
void upd(ll cl, ll cr, ll lf, ll rg, ll nd, ll valmn, ll valmx){
	if(cl==cr) ans[cl]=stmax[nd];
	else if(stmin[nd]!=inf || stmax[nd]!=0){
		down(nd*2, stmin[nd], stmax[nd]);
		down(nd*2+1, stmin[nd], stmax[nd]);
		stmin[nd]=inf;
		stmax[nd]=0;
	}
	if(cr<lf || rg<cl) return;
	else if(lf<=cl && cr<=rg)
		down(nd, valmn, valmx);
	else{
		upd(cl, (cl+cr)/2, lf, rg, nd*2, valmn, valmx);
		upd((cl+cr)/2, cr, lf, rg, nd*2+1, valmn, valmx);
	}
}
void buildWall(int n, int k, int op[], int lf[], int rg[], int H[], int fh[]){
	stmax.resize(4*n+1); stmin.resize(4*n+1); ans.resize(n+1);
	for(int i=1; i<=4*n; i++) {stmin[i]=inf; stmax[i]=0;}
	for(int i=0; i<k; i++){
		if(op[i]==1)
			upd(0, n-1, lf[i], rg[i], 1, inf, H[i]);
		else
			upd(0, n-1, lf[i], rg[i], 1, H[i], 0);
	}
	for(int i=0; i<n; i++)
		upd(0, n-1, i, i, 1, inf, 0);
	for(int i=0; i<n; i++)
		fh[i]=ans[i];
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 171 ms 8192 KB Output is correct
3 Runtime error 96 ms 9720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -