| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1119965 |
2024-11-27T16:02:59 Z |
Newtonabc |
Wall (IOI14_wall) |
C++14 |
|
1 ms |
340 KB |
#include "wall.h"
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=1<<22;
pair<int,int> s[N],lz[N];
pair<int,int> merge(pair<int,int> a,pair<int,int> b){
if(a.first==-1 && a.second==-1) return b;
if(b.first>a.second) return {b.first,b.first};
if(b.second<a.first) return {b.second,b.second};
return {max(a.first,b.first),min(a.second,b.second)};
}
pair<int,int> add(pair<int,int> a,pair<int,int> b){
return {min(a.first,b.first),max(a.second,b.second)};
}
void buildlz(int l,int r,int idx){
lz[idx]={-1,-1};
if(l==r) return;
int m=(l+r)/2;
buildlz(l,m,idx*2);
buildlz(m+1,r,idx*2+1);
}
void pushlz(int l,int r,int idx){
if(lz[idx]==mp(-1,-1)) return;
s[idx]=merge(s[idx],lz[idx]);
if(l!=r) lz[idx*2]=merge(lz[idx*2],lz[idx]),lz[idx*2+1]=merge(lz[idx*2+1],lz[idx]);
lz[idx]={-1,-1};
}
void update(int l,int r,int idx,int a,int b,int type,int val){
pushlz(l,r,idx);
if(a>r || b<l) return;
if(a<=l && b>=r){
if(type==1) lz[idx]=merge(lz[idx],mp(val,INT_MAX));
else lz[idx]=merge(lz[idx],mp(INT_MIN,val));
pushlz(l,r,idx);
return;
}
int m=(l+r)/2;
update(l,m,idx*2,a,b,type,val);
update(m+1,r,idx*2+1,a,b,type,val);
s[idx]=add(s[idx*2],s[idx*2+1]);
}
int query(int l,int r,int idx,int a){
pushlz(l,r,idx);
if(a>r || a<l) return 0;
if(l==r) return s[idx].first;
int m=(l+r)/2;
return query(l,m,idx*2,a)+query(m+1,r,idx*2+1,a);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
buildlz(0,n-1,1);
for(int i=0;i<k;i++){
update(0,n-1,1,left[i],right[i],op[i],height[i]);
//for(int i=1;i<=26;i++) cout<<i <<" " <<s[i].first <<" " <<s[i].second <<" " <<lz[i].first <<" " <<lz[i].second <<"\n";
//cout<<"---------------------------\n";
}
for(int i=0;i<n-1;i++) finalHeight[i]=query(0,n-1,1,i);
return;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
