oj.uz

답안 #1062888

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1062888 2024-08-17T11:35:30 Z YassirSalama 벽 (IOI14_wall) C++17
32 / 100
 3000 ms 29780 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 100;
template<typename T>
void dbg(const T& t){
  cout<<t<<endl;
  return;
}
template<typename T,typename... Args>
void dbg(const T& t,const Args&... args){
  cout<<t<<" , ";
  dbg(args...);
}
#define dbg(...) cout<<"("<<#__VA_ARGS__<<") : "<<endl;dbg(__VA_ARGS__);

struct Node
{
  int min;
  int max;
  int smin;
  int smax;
  int lzmin=-1,lzmax=-1;
  bool lazy=false;
  Node* left,*right;
  Node() : left(nullptr),right(nullptr){}
};
void pull(Node* node){
  //for min
  node->min=min(node->left->min,node->right->min);
  if(node->left->min==node->right->min){
    node->smin=min(node->left->smin,node->right->smin);
  }else if(node->left->min==node->min){
    node->smin=min(node->left->smin,node->right->min);
  }else node->smin=min(node->right->smin,node->left->min);
  
  //for max
  node->max=max(node->left->max,node->right->max);
  if(node->left->max==node->right->max){
    node->smax=max(node->left->smax,node->right->max);
  }else if(node->left->max==node->max){
    node->smax=max(node->left->smax,node->right->max);
  }else node->smax=max(node->right->smax,node->left->max);
}
void build(Node* node,int l,int r){
  if(l==r){
    node->min=node->max=0;
    node->smin=1e9;
    node->smax=-1e9;
    return;
  }
  int mid=(l+r)/2;
  node->left=new Node();
  node->right=new Node();
  build(node->left,l,mid);
  build(node->right,mid+1,r);
  pull(node);
}
void pmin(Node* node,int l,int r,int x){
  if(node->max<=x) return;
  node->max=x;
  if(l==r){
    node->min=node->max;
  }else{
    if(x<=node->min){
      node->min=x;
    }else if(x<node->smin){
      node->smin=x;
    }
  }
}
void pmax(Node* node,int l,int r,int x){
  if(node->min>=x)
    return;
  node->min=x;
  if(l==r){
    node->max=node->min;
  }else{
    if(x>=node->max){
      node->max=x;
    }else if(x>node->smax){
      node->smax=x;
    }
  }
}
void push(Node* node,int l,int r){
  if(l==r) return;
  pmin(node->left,l,(l+r)/2,node->max);
  pmin(node->right,(l+r)/2+1,r,node->max);
  pmax(node->left,l,(l+r)/2,node->min);
  pmax(node->right,(l+r)/2+1,r,node->min);
}
void setmin(Node* node,int l,int r,int ql,int qr,int x){
  push(node,l,r);
  if(l>qr||r<ql) return;
  if(node->max<=x) return;
  if(ql<=l&&r<=qr&&node->smax<x){
    //put tag
    pmin(node,l,r,x);
    return;
  }
  push(node,l,r);
  int mid=(l+r)/2;
  setmin(node->left,l,mid,ql,qr,x);
  setmin(node->right,mid+1,r,ql,qr,x);
  pull(node);
}
void setmax(Node* node,int l,int r,int ql,int qr,int x){
  push(node,l,r);
  if(l>qr||r<ql) return;
  if(node->min>=x) return;
  if(ql<=l&&r<=qr&&x<node->smin){
    //put tag
    pmax(node,l,r,x);
    return;
  }
  push(node,l,r);
  int mid=(l+r)/2;
  setmax(node->left,l,mid,ql,qr,x);
  setmax(node->right,mid+1,r,ql,qr,x);
  pull(node);
}
int query(Node* node,int l,int r,int ql){
  push(node,l,r);
  if(l==r) return node->min;
  int mid = (l+r)/2;
  if(ql<=mid) return query(node->left,l,mid,ql);
  else return query(node->right,mid+1,r,ql);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int ans[])
{
  Node* root=new Node();
  build(root,0,n-1);
  for(int i=0;i<k;i++){
    int t=op[i];
    int l=left[i];
    int r=right[i];
    int x=height[i];
    if(t==1){
      setmax(root,0,n-1,l,r,x);
    }else{
      setmin(root,0,n-1,l,r,x);
    }
  }
  for(int i=0;i<n;i++){
    ans[i]=query(root,0,n-1,i);
  }
  return;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 10 ms 1896 KB Output is correct
5 Correct 6 ms 1884 KB Output is correct
6 Correct 6 ms 1884 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 107 ms 12688 KB Output is correct
3 Correct 53 ms 9044 KB Output is correct
4 Correct 152 ms 29012 KB Output is correct
5 Correct 149 ms 29640 KB Output is correct
6 Correct 176 ms 28756 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 576 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 10 ms 1884 KB Output is correct
5 Correct 5 ms 1884 KB Output is correct
6 Correct 6 ms 1884 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 95 ms 12800 KB Output is correct
9 Correct 51 ms 9040 KB Output is correct
10 Correct 134 ms 28904 KB Output is correct
11 Correct 136 ms 29744 KB Output is correct
12 Correct 180 ms 28848 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 83 ms 12704 KB Output is correct
15 Correct 60 ms 3668 KB Output is correct
16 Correct 1284 ms 29080 KB Output is correct
17 Execution timed out 3003 ms 29780 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 10 ms 1888 KB Output is correct
5 Correct 6 ms 1912 KB Output is correct
6 Correct 6 ms 1884 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 81 ms 12704 KB Output is correct
9 Correct 49 ms 9040 KB Output is correct
10 Correct 138 ms 28972 KB Output is correct
11 Correct 140 ms 29640 KB Output is correct
12 Correct 173 ms 28756 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 87 ms 12852 KB Output is correct
15 Correct 55 ms 3668 KB Output is correct
16 Correct 1342 ms 29232 KB Output is correct
17 Execution timed out 3072 ms 29656 KB Time limit exceeded
18 Halted 0 ms 0 KB -