oj.uz

Submission #703333

# Submission time Handle Problem Language Result Execution time Memory
703333 2023-02-27T04:46:52 Z jamezzz Wall (IOI14_wall) C++17
100 / 100
 1251 ms 124688 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int,int> ii;
#define all(x) x.begin(),x.end()
#define disc(d) sort(all(d));d.resize(unique(all(d))-d.begin());
#define maxn 2000005
#define INF 1023456789
 
struct node{
	int s,e,m,mn,mx,lzmn,lzmx;//value has to between [mn, mx];
	node *l,*r;
	node(int _s,int _e){
		s=_s,e=_e,m=(s+e)>>1,mn=0,mx=INF,lzmn=0,lzmx=INF;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	ii join(ii l,ii r){
		auto[lmn,lmx]=l;
		auto[rmn,rmx]=r;
		if(max(lmn,rmn)<=min(lmx,rmx))return {max(lmn,rmn),min(lmx,rmx)};
		else if(rmx<=lmn)return {rmx,rmx};
		else return {rmn,rmn};
	}
	void ppo(){
		tie(mn,mx)=join({mn,mx},{lzmn,lzmx});
		if(s!=e){
			tie(l->lzmn,l->lzmx)=join({l->lzmn,l->lzmx},{lzmn,lzmx});
			tie(r->lzmn,r->lzmx)=join({r->lzmn,r->lzmx},{lzmn,lzmx});
		}
		lzmn=0,lzmx=INF;
	}
	void up(int x,int y,int type,int h){
		ppo();
		if(s==x&&e==y){
			if(type==1)tie(lzmn,lzmx)=join({lzmn,lzmx},{h,INF});
			else tie(lzmn,lzmx)=join({lzmn,lzmx},{0,h});
			return;
		}
		if(y<=m)l->up(x,y,type,h);
		else if(x>m)r->up(x,y,type,h);
		else{
			l->up(x,m,type,h);
			r->up(m+1,y,type,h);
		}
		l->ppo(),r->ppo();
		tie(mn,mx)=join({l->mn,l->mx},{r->mn,r->mx});
	}
	ii qry(int x){
		ppo();
		if(s==x&&e==x)return {mn,mx};
		if(x<=m)return l->qry(x);
		else return r->qry(x);
	}
}*rt;
 
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
	vector<int> d;
	for(int i=0;i<k;++i)d.push_back(left[i]),d.push_back(right[i]+1);
	disc(d);
	rt=new node(0,d.size()-1);
	for(int i=0;i<k;++i){
		int l=lower_bound(all(d),left[i])-d.begin();
		int r=lower_bound(all(d),right[i]+1)-d.begin();
		rt->up(l,r-1,op[i],height[i]);
	}
	vector<int> ans;
	ans.resize(d.size(),0);
	for(int i=0;i<d.size();++i){
		ans[i]=rt->qry(i).first;
	}
	d.push_back(n+1);
	for(int i=0;i<d.size()-1;++i){
		int l=d[i],r=d[i+1]-1;
		for(int j=l;j<=r;++j)finalHeight[j]=ans[i];
	}
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i=0;i<d.size();++i){
      |              ~^~~~~~~~~
wall.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i=0;i<d.size()-1;++i){
      |              ~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 11 ms 1420 KB Output is correct
5 Correct 7 ms 1176 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 163 ms 12604 KB Output is correct
3 Correct 299 ms 7800 KB Output is correct
4 Correct 1139 ms 25596 KB Output is correct
5 Correct 430 ms 19092 KB Output is correct
6 Correct 420 ms 19132 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 308 KB Output is correct
4 Correct 13 ms 1364 KB Output is correct
5 Correct 8 ms 1172 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 165 ms 12608 KB Output is correct
9 Correct 297 ms 7868 KB Output is correct
10 Correct 1075 ms 25608 KB Output is correct
11 Correct 458 ms 19088 KB Output is correct
12 Correct 423 ms 19208 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 160 ms 12592 KB Output is correct
15 Correct 64 ms 3376 KB Output is correct
16 Correct 1228 ms 25596 KB Output is correct
17 Correct 448 ms 19128 KB Output is correct
18 Correct 458 ms 19252 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 11 ms 1336 KB Output is correct
5 Correct 7 ms 1172 KB Output is correct
6 Correct 7 ms 1200 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 161 ms 12508 KB Output is correct
9 Correct 295 ms 7908 KB Output is correct
10 Correct 1049 ms 25540 KB Output is correct
11 Correct 417 ms 19224 KB Output is correct
12 Correct 413 ms 19104 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 165 ms 12572 KB Output is correct
15 Correct 64 ms 3392 KB Output is correct
16 Correct 1251 ms 25656 KB Output is correct
17 Correct 448 ms 19176 KB Output is correct
18 Correct 447 ms 19288 KB Output is correct
19 Correct 1135 ms 124688 KB Output is correct
20 Correct 1124 ms 122176 KB Output is correct
21 Correct 1120 ms 124616 KB Output is correct
22 Correct 1131 ms 122280 KB Output is correct
23 Correct 1138 ms 119884 KB Output is correct
24 Correct 1107 ms 118620 KB Output is correct
25 Correct 1110 ms 118380 KB Output is correct
26 Correct 1127 ms 121032 KB Output is correct
27 Correct 1132 ms 121032 KB Output is correct
28 Correct 1117 ms 118400 KB Output is correct
29 Correct 1138 ms 118428 KB Output is correct
30 Correct 1113 ms 118624 KB Output is correct