oj.uz

답안 #1119965

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1119965 2024-11-27T16:02:59 Z Newtonabc 벽 (IOI14_wall) C++14
0 / 100
 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;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -