| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 856316 |
2023-10-03T05:47:59 Z |
vipboy0402hcm |
Wall (IOI14_wall) |
C++17 |
|
166 ms |
14024 KB |
#include<iostream>
#include<vector>
#include<cmath>
#include<stdio.h>
#include<numeric>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<algorithm>
#include<string>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef unsigned long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
struct lazy{
ll height;
ll type;
ll query;
};
lazy ar[8000017];
vector<ii> res;
ll n,m,u,v,q,k,t;
/*void build(int id,int l,int r){
if(l==r){
ar[id]=0x3f3f3f3f;
return;
}
int m=(l+r)/2;
build(2*id,l,m);
build(2*id+1,m+1,r);
ar[id]=min(ar[2*id],ar[2*id+1]);
}
void apply(ll& a,lazy b,int len){
if(b.a==0&&b.d==0){
return;
}
else{
a=b.assign*len;
a+=b.add*len;
}
}*/
void apply(lazy& a,lazy b){
if(b.type==0){
return;
}
else if(b.type==1){
a.height=max(a.height,b.query);
a.query=b.query;
a.type=b.type;
}
else{
a.height=min(a.height,b.query);
a.query=b.query;
a.type=b.type;
}
}
void propagate(int id,int l,int r){
if(l==r){
return;
}
apply(ar[2*id],ar[id]);
apply(ar[2*id+1],ar[id]);
}
void print(int id,int l,int r,int finalHeight[]){
if(l==r){
finalHeight[l]=ar[id].height;
return;
}
int m=(l+r)/2;
print(2*id,l,m,finalHeight);
print(2*id+1,m+1,r,finalHeight);
}
void propagateAll(int id,int l,int r){
propagate(id,l,r);
ar[id]={ar[id].height,0,0};
if(l==r){
return;
}
int m=(l+r)/2;
propagateAll(2*id,l,m);
propagateAll(2*id+1,m+1,r);
}
void add(int id,int lx,int rx,int l,int r,ll t,ll a){
propagate(id,lx,rx);
ar[id]={ar[id].height,0,0};
if(rx<l||lx>r){
return;
}
if(lx>=l&&rx<=r){
ar[id].height=t==1 ? max(ar[id].height,a) : min(ar[id].height,a);
ar[id].query=a;
ar[id].type=t;
propagate(id,lx,rx);
ar[id]={ar[id].height,0,0};
return;
}
int m=(lx+rx)/2;
add(2*id,lx,m,l,r,t,a);
add(2*id+1,m+1,rx,l,r,t,a);
}
/*segment get(int id,int lx,int rx,int l,int r){
apply(res[id],ar[id],rx-lx+1);
propagate(id,lx,rx);
ar[id]=0;
if(rx<l||lx>r){
return {0,0,0,0};
}
else if(lx>=l&&rx<=r){
return res[id];
}
int m=(lx+rx)/2;
segment a=get(2*id,lx,m,l,r);
segment b=get(2*id+1,m+1,rx,l,r);
return merge(a,b);
}
int find(int id,int l,int r,ll k,ll index){
if(ar[id]!=0){
res[id]+=ar[id];
if(r!=l){
ar[2*id]+=ar[id];
ar[2*id+1]+=ar[id];
}
ar[id]=0;
}
if(index>r){
return -1;
}
if(k>res[id]){
return -1;
}
if(l==r){
return l;
}
int m=(l+r)/2;
int res=find(2*id,l,m,k,index);
if(res==-1){
res=find(2*id+1,m+1,r,k,index);
}
return res;
}*/
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<k;i++){
add(1,0,n-1,left[i],right[i],op[i],height[i]);
}
propagateAll(1,0,n-1);
print(1,0,n-1,finalHeight);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
112 ms |
14024 KB |
Output is correct |
| 3 |
Incorrect |
166 ms |
9044 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
456 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
