oj.uz

Submission #1119986

# Submission time Handle Problem Language Result Execution time Memory
1119986 2024-11-27T16:25:24 Z Newtonabc Wall (IOI14_wall) C++14
100 / 100
 1280 ms 102472 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;i++) finalHeight[i]=query(0,n-1,1,i);
  
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 9 ms 1108 KB Output is correct
5 Correct 6 ms 1108 KB Output is correct
6 Correct 9 ms 1108 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 159 ms 14056 KB Output is correct
3 Correct 254 ms 8484 KB Output is correct
4 Correct 912 ms 22532 KB Output is correct
5 Correct 272 ms 23588 KB Output is correct
6 Correct 263 ms 22028 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 580 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 11 ms 1108 KB Output is correct
5 Correct 6 ms 1108 KB Output is correct
6 Correct 9 ms 1108 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 131 ms 13868 KB Output is correct
9 Correct 303 ms 8580 KB Output is correct
10 Correct 845 ms 22532 KB Output is correct
11 Correct 327 ms 23112 KB Output is correct
12 Correct 270 ms 22016 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 116 ms 13924 KB Output is correct
15 Correct 56 ms 2548 KB Output is correct
16 Correct 872 ms 22780 KB Output is correct
17 Correct 286 ms 22192 KB Output is correct
18 Correct 299 ms 22196 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 3 ms 456 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 10 ms 1160 KB Output is correct
5 Correct 6 ms 1108 KB Output is correct
6 Correct 7 ms 1224 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 135 ms 14036 KB Output is correct
9 Correct 267 ms 8636 KB Output is correct
10 Correct 920 ms 22532 KB Output is correct
11 Correct 353 ms 23596 KB Output is correct
12 Correct 336 ms 21972 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 122 ms 14084 KB Output is correct
15 Correct 51 ms 2796 KB Output is correct
16 Correct 932 ms 22960 KB Output is correct
17 Correct 393 ms 22092 KB Output is correct
18 Correct 424 ms 22204 KB Output is correct
19 Correct 1280 ms 102384 KB Output is correct
20 Correct 1234 ms 99820 KB Output is correct
21 Correct 1091 ms 102412 KB Output is correct
22 Correct 1179 ms 99132 KB Output is correct
23 Correct 1065 ms 99832 KB Output is correct
24 Correct 1049 ms 99996 KB Output is correct
25 Correct 1098 ms 99916 KB Output is correct
26 Correct 1258 ms 102424 KB Output is correct
27 Correct 1112 ms 102472 KB Output is correct
28 Correct 1116 ms 99876 KB Output is correct
29 Correct 1130 ms 99840 KB Output is correct
30 Correct 1157 ms 99864 KB Output is correct