oj.uz

Submission #139949

# Submission time Handle Problem Language Result Execution time Memory
139949 2019-08-01T17:40:19 Z MrBrionix Wall (IOI14_wall) C++14
100 / 100
 739 ms 115120 KB 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
#define INF 100005

int v[2000005],l,r;
pair<int,int> q;
pair<int,int> rt[9000000];

inline pair<int,int> unite(pair<int,int> a,pair<int,int> b){
    pair<int,int> tmp;
    
    tmp.second=max(b.first,min(b.second,a.second));
    tmp.first=min(b.second,max(b.first,a.first));
    
    return tmp;    
}

inline void push(int pos){
    
    rt[pos*2]=unite(rt[pos],rt[pos*2]);
    rt[pos*2+1]=unite(rt[pos],rt[pos*2+1]);
    
    rt[pos]={0,INF};  
}

void upd(int pos,int _l,int _r){

    if(r<_l || l>_r)return;
    
    if(_l>=l && _r<=r){
        rt[pos]=unite(q,rt[pos]);
        return;    
    }
    
    push(pos);
    
    upd(pos*2,_l,(_l+_r)/2);
    upd(pos*2+1,(_l+_r)/2+1,_r);
}

void query(int pos,int _l,int _r,int val){

    if(val<rt[pos].first)val=rt[pos].first;
    if(val>rt[pos].second)val=rt[pos].second;

    if(_l==_r){
        v[_l]=val;
        return;    
    }
    
    query(pos*2,_l,(_l+_r)/2,val);
    query(pos*2+1,(_l+_r)/2+1,_r,val);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  
    for(int i=0;i<9000000;i++)rt[i].second=INF;
    
    
    for(int i=k-1;i>=0;i--){   
        l=left[i];
        r=right[i];
        if(op[i]==1){
            q.first=height[i];
            q.second=INF; 
        }
        else{
            q.first=0;
            q.second=height[i];    
        }
        
        upd(1,0,n-1);
    }
    
    query(1,0,n-1,0);
  
    for(int i=0;i<n;i++){
    finalHeight[i]=v[i];   
    }
  
    return;
}
/*
int main()
{
  int n;
  int k;

  int i, j;  
  int status = 0;

  status = scanf("%d%d", &n, &k);
  assert(status == 2);

  int* op = (int*)calloc(sizeof(int), k);
  int* left = (int*)calloc(sizeof(int), k);
  int* right = (int*)calloc(sizeof(int), k);
  int* height = (int*)calloc(sizeof(int), k);
  int* finalHeight = (int*)calloc(sizeof(int), n);

  for (i = 0; i < k; i++){
    status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
    assert(status == 4);
  }

  buildWall(n, k, op, left, right, height, finalHeight);

  for (j = 0; j < n; j++)
    printf("%d\n", finalHeight[j]);
  
  return 0;
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 70776 KB Output is correct
2 Correct 60 ms 70904 KB Output is correct
3 Correct 60 ms 70904 KB Output is correct
4 Correct 74 ms 71032 KB Output is correct
5 Correct 63 ms 71160 KB Output is correct
6 Correct 63 ms 71076 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 70908 KB Output is correct
2 Correct 233 ms 84452 KB Output is correct
3 Correct 244 ms 78068 KB Output is correct
4 Correct 570 ms 89256 KB Output is correct
5 Correct 370 ms 90252 KB Output is correct
6 Correct 358 ms 88824 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 70776 KB Output is correct
2 Correct 60 ms 70872 KB Output is correct
3 Correct 59 ms 70860 KB Output is correct
4 Correct 62 ms 71160 KB Output is correct
5 Correct 62 ms 71228 KB Output is correct
6 Correct 63 ms 71032 KB Output is correct
7 Correct 57 ms 70776 KB Output is correct
8 Correct 233 ms 84488 KB Output is correct
9 Correct 238 ms 78072 KB Output is correct
10 Correct 572 ms 89180 KB Output is correct
11 Correct 372 ms 90248 KB Output is correct
12 Correct 363 ms 88696 KB Output is correct
13 Correct 57 ms 70776 KB Output is correct
14 Correct 241 ms 84472 KB Output is correct
15 Correct 86 ms 72056 KB Output is correct
16 Correct 579 ms 89720 KB Output is correct
17 Correct 361 ms 88824 KB Output is correct
18 Correct 363 ms 88952 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 70752 KB Output is correct
2 Correct 59 ms 70896 KB Output is correct
3 Correct 58 ms 70776 KB Output is correct
4 Correct 63 ms 71076 KB Output is correct
5 Correct 62 ms 71032 KB Output is correct
6 Correct 62 ms 71032 KB Output is correct
7 Correct 57 ms 70776 KB Output is correct
8 Correct 231 ms 84504 KB Output is correct
9 Correct 238 ms 78072 KB Output is correct
10 Correct 565 ms 89208 KB Output is correct
11 Correct 368 ms 90360 KB Output is correct
12 Correct 365 ms 88720 KB Output is correct
13 Correct 64 ms 70776 KB Output is correct
14 Correct 236 ms 84484 KB Output is correct
15 Correct 87 ms 71980 KB Output is correct
16 Correct 573 ms 89624 KB Output is correct
17 Correct 362 ms 88864 KB Output is correct
18 Correct 367 ms 88924 KB Output is correct
19 Correct 729 ms 114984 KB Output is correct
20 Correct 739 ms 112560 KB Output is correct
21 Correct 731 ms 114904 KB Output is correct
22 Correct 723 ms 112504 KB Output is correct
23 Correct 726 ms 112572 KB Output is correct
24 Correct 724 ms 112632 KB Output is correct
25 Correct 721 ms 112632 KB Output is correct
26 Correct 733 ms 115120 KB Output is correct
27 Correct 727 ms 114932 KB Output is correct
28 Correct 721 ms 112400 KB Output is correct
29 Correct 730 ms 112396 KB Output is correct
30 Correct 727 ms 112584 KB Output is correct