oj.uz

Submission #1062897

# Submission time Handle Problem Language Result Execution time Memory
1062897 2024-08-17T11:44:10 Z YassirSalama Wall (IOI14_wall) C++17
32 / 100
 3000 ms 23632 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 100;
struct Node{
  int min;
  int max;
  int smin;
  int smax;
} tree[4*maxn];
void pull(int node){
  //for min
  tree[node].min=min(tree[node*2].min,tree[node*2+1].min);
  if(tree[node*2].min==tree[node*2+1].min){
    tree[node].smin=min(tree[node*2].smin,tree[node*2+1].smin);
  }else if(tree[node*2].min==tree[node].min){
    tree[node].smin=min(tree[node*2].smin,tree[node*2+1].min);
  }else tree[node].smin=min(tree[node*2+1].smin,tree[node*2].min);
  //for max
  tree[node].max=max(tree[node*2].max,tree[node*2+1].max);
  if(tree[node*2].max==tree[node*2+1].max){
    tree[node].smax=max(tree[node*2].smax,tree[node*2+1].max);
  }else if(tree[node*2].max==tree[node].max){
    tree[node].smax=max(tree[node*2].smax,tree[node*2+1].max);
  }else tree[node].smax=max(tree[node*2+1].smax,tree[node*2].max);
}
void build(int node,int l,int r){
  if(l==r){
    tree[node].min=tree[node].max=0;
    tree[node].smin=1e9;
    tree[node].smax=-1e9;
    return;
  }
  int mid=(l+r)/2;
  build(node*2,l,mid);
  build(node*2+1,mid+1,r);
  pull(node);
}
void pmin(int node,int l,int r,int x){
  if(tree[node].max<=x) return;
  tree[node].max=x;
  if(l==r){
    tree[node].min=tree[node].max;
  }else{
    if(x<=tree[node].min){
      tree[node].min=x;
    }else if(x<tree[node].smin){
      tree[node].smin=x;
    }
  }
}
void pmax(int node,int l,int r,int x){
  if(tree[node].min>=x)
    return;
  tree[node].min=x;
  if(l==r){
    tree[node].max=tree[node].min;
  }else{
    if(x>=tree[node].max){
      tree[node].max=x;
    }else if(x>tree[node].smax){
      tree[node].smax=x;
    }
  }
}
void push(int node,int l,int r){
  if(l==r) return;
  pmin(node*2,l,(l+r)/2,tree[node].max);
  pmin(node*2+1,(l+r)/2+1,r,tree[node].max);
  pmax(node*2,l,(l+r)/2,tree[node].min);
  pmax(node*2+1,(l+r)/2+1,r,tree[node].min);
}
void setmin(int node,int l,int r,int ql,int qr,int x){
  push(node,l,r);
  if(l>qr||r<ql||tree[node].max<=x) return;
  if(ql<=l&&r<=qr&&tree[node].smax<x){
    //put tag
    pmin(node,l,r,x);
    return;
  }
  push(node,l,r);
  int mid=(l+r)/2;
  setmin(node*2,l,mid,ql,qr,x);
  setmin(node*2+1,mid+1,r,ql,qr,x);
  pull(node);
}
void setmax(int node,int l,int r,int ql,int qr,int x){
  push(node,l,r);
  if(l>qr||r<ql||tree[node].min>=x) return;
  if(ql<=l&&r<=qr&&x<tree[node].smin){
    //put tag
    pmax(node,l,r,x);
    return;
  }
  push(node,l,r);
  int mid=(l+r)/2;
  setmax(node*2,l,mid,ql,qr,x);
  setmax(node*2+1,mid+1,r,ql,qr,x);
  pull(node);
}
int query(int node,int l,int r,int ql){
  push(node,l,r);
  if(l==r) return tree[node].min;
  int mid = (l+r)/2;
  if(ql<=mid) return query(node*2,l,mid,ql);
  else return query(node*2+1,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(1,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(1,0,n-1,l,r,x);
    }else{
      setmin(1,0,n-1,l,r,x);
    }
  }
  for(int i=0;i<n;i++){
    ans[i]=query(1,0,n-1,i);
  }
  return;
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:110:9: warning: unused variable 'root' [-Wunused-variable]
  110 |   Node* root=new Node();
      |         ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 12 ms 1168 KB Output is correct
5 Correct 7 ms 1116 KB Output is correct
6 Correct 7 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 84 ms 13884 KB Output is correct
3 Correct 55 ms 8532 KB Output is correct
4 Correct 152 ms 22388 KB Output is correct
5 Correct 176 ms 23380 KB Output is correct
6 Correct 235 ms 21844 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 19 ms 1164 KB Output is correct
5 Correct 8 ms 1220 KB Output is correct
6 Correct 8 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 96 ms 14080 KB Output is correct
9 Correct 56 ms 8532 KB Output is correct
10 Correct 153 ms 22552 KB Output is correct
11 Correct 163 ms 23376 KB Output is correct
12 Correct 237 ms 22016 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 97 ms 13948 KB Output is correct
15 Correct 74 ms 2644 KB Output is correct
16 Correct 1668 ms 22612 KB Output is correct
17 Execution timed out 3039 ms 21332 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory 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 14 ms 1164 KB Output is correct
5 Correct 9 ms 1112 KB Output is correct
6 Correct 8 ms 1112 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 83 ms 14160 KB Output is correct
9 Correct 57 ms 8532 KB Output is correct
10 Correct 196 ms 22476 KB Output is correct
11 Correct 161 ms 23632 KB Output is correct
12 Correct 228 ms 21840 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 83 ms 13932 KB Output is correct
15 Correct 75 ms 2644 KB Output is correct
16 Correct 1656 ms 22748 KB Output is correct
17 Execution timed out 3095 ms 21328 KB Time limit exceeded
18 Halted 0 ms 0 KB -