oj.uz

Submission #294489

# Submission time Handle Problem Language Result Execution time Memory
294489 2020-09-09T01:12:05 Z Hemimor Wall (IOI14_wall) C++14
100 / 100
 794 ms 67836 KB 
#include "wall.h"
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Lazy_Segment_Tree{
	private:
	int n;
	vp date;
	int f(int x,P p){
		if(x<p.first) return p.first;
		if(p.second<x) return p.second;
		return x;
	}
	void Set_Lazy(int k,P p){
		date[k]={f(date[k].first,p),f(date[k].second,p)};
	}
	void Push(int k){
		Set_Lazy(k*2+1,date[k]);
		Set_Lazy(k*2+2,date[k]);
		date[k]={-inf,inf};
	}
	void Rec(int a,int b,int k,int l,int r,P p){
		if(r<=a||b<=l) return;
		if(a<=l&&r<=b){
			Set_Lazy(k,p);
			return;
		}
		Push(k);
		int m=(l+r)/2;
		Rec(a,b,k*2+1,l,m,p);
		Rec(a,b,k*2+2,m,r,p);
	}
	public:
	Lazy_Segment_Tree(int n_){
		n=1;
		while(n<n_) n*=2;
		date=vp(2*n-1,{-inf,inf});
	}
	void Query(int a,int b,P p){
		return Rec(a,b,0,0,n,p);
	}
	vi Open(){
		vi a(n);
		for(int i=0;i<n-1;i++) Push(i);
		for(int i=0;i<n;i++) a[i]=f(0,date[i+n-1]);
		return a;
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	Lazy_Segment_Tree st(n);
	for(int i=0;i<k;i++){
		if(op[i]==1) st.Query(left[i],right[i]+1,{height[i],inf});
		else st.Query(left[i],right[i]+1,{-inf,height[i]});
	}
	vi a=st.Open();
	for(int i=0;i<n;i++) finalHeight[i]=a[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 183 ms 14072 KB Output is correct
3 Correct 230 ms 8184 KB Output is correct
4 Correct 567 ms 20728 KB Output is correct
5 Correct 356 ms 21368 KB Output is correct
6 Correct 332 ms 19756 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 181 ms 14016 KB Output is correct
9 Correct 228 ms 8184 KB Output is correct
10 Correct 556 ms 20804 KB Output is correct
11 Correct 349 ms 21240 KB Output is correct
12 Correct 330 ms 19832 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 184 ms 14004 KB Output is correct
15 Correct 40 ms 2040 KB Output is correct
16 Correct 666 ms 21244 KB Output is correct
17 Correct 346 ms 20344 KB Output is correct
18 Correct 345 ms 20152 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 181 ms 14124 KB Output is correct
9 Correct 228 ms 8120 KB Output is correct
10 Correct 560 ms 20856 KB Output is correct
11 Correct 350 ms 21240 KB Output is correct
12 Correct 338 ms 19880 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 182 ms 14080 KB Output is correct
15 Correct 39 ms 2048 KB Output is correct
16 Correct 673 ms 20872 KB Output is correct
17 Correct 343 ms 20216 KB Output is correct
18 Correct 346 ms 20292 KB Output is correct
19 Correct 794 ms 67800 KB Output is correct
20 Correct 786 ms 67704 KB Output is correct
21 Correct 793 ms 67704 KB Output is correct
22 Correct 783 ms 67576 KB Output is correct
23 Correct 783 ms 67576 KB Output is correct
24 Correct 779 ms 67624 KB Output is correct
25 Correct 776 ms 67576 KB Output is correct
26 Correct 784 ms 67448 KB Output is correct
27 Correct 786 ms 67836 KB Output is correct
28 Correct 777 ms 67576 KB Output is correct
29 Correct 786 ms 67576 KB Output is correct
30 Correct 791 ms 67672 KB Output is correct