oj.uz

답안 #205248

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
205248 2020-02-28T11:20:07 Z awlintqaa 벽 (IOI14_wall) C++14
0 / 100
 1087 ms 8184 KB 
#include <bits/stdc++.h>
using namespace std;
#define sqr 200
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1e9+7;
const ll inf= 2e9;
const ld pai=acos(-1);
#include "wall.h"
struct NODE{
        int tree,on,mn,mx;
        NODE *left,*right;
        NODE(){
                tree=on=0;
                mn=-inf,mx=inf;
                left=right=NULL;
        }
}*root=new NODE;
void fill(NODE *pre,NODE *node){
        if(node->on==0){
                node->on=pre->on;
                node->mn=pre->mn;
                node->mx=pre->mx;
                return ;
        }
        node->mn=max(node->mn,pre->mn);
        node->mx=max(node->mx,pre->mx);
        node->mx=min(node->mx,pre->mx);
        node->mn=min(node->mn,pre->mx);
}
void lzyUPD(NODE *node,int l,int r){
        if(node->on==0)return ;
        node->tree=max(node->tree,node->mn);
        node->tree=min(node->tree,node->mx);
        if(l!=r){
                if(node->left==NULL)node->left=new NODE;
                if(node->right==NULL)node->right=new NODE;
                fill(node,node->left);
                fill(node,node->right);
        }
        node->on=0;
        node->mn=-inf;
        node->mx=inf;
}
void upd(NODE *node,int l,int r,int s,int e,int x,int t){;
        lzyUPD(node,l,r);
        if ( s>r || e<l ) return ;
        if(s<=l && e>=r){
                if(t==1)node->mn=x,node->mx=inf;
                if(t==2)node->mn=-inf,node->mx=x;
                node->on=1;
                lzyUPD(node,l,r);
                return ;
        }
        if(node->left==NULL)node->left=new NODE;
        if(node->right==NULL)node->right=new NODE;
        upd(node->left,l,mid,s,e,x,t);
        upd(node->right,mid+1,r,s,e,x,t);
        node->tree = max ( node->left->tree , node->right->tree ) ;
}
int a[100009];
int check(int l,int r){
  for(int i=l;i<=r;i++){
    if(a[i])return 1;
  }
  return 0;
}
int query(NODE *node,int l,int r,int id){
        lzyUPD(node,l,r);
        if(l==r)return node->tree;
        if(id<=mid){
                if(node->left==NULL && check(l,r))while(1){};
                return query(node->left,l,mid,id);
        }
        if(node->right==NULL && check(l,r))while(1){}
        return query(node->right,mid+1,r,id);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
        for(int i=0;i<k;i++)upd(root,0,n-1,left[i],right[i],height[i],op[i]);
  		for(int i=0;i<k;i++){
          for(int j=left[i];j<=right[i];j++){
            a[j]++;
          }
        }
        for(int i=0;i<n;i++)finalHeight[i]=query(root,0,n-1,i);
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Incorrect 7 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 179 ms 8184 KB Output is correct
3 Incorrect 1087 ms 5604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Incorrect 7 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Incorrect 7 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -