oj.uz

Submission #768666

# Submission time Handle Problem Language Result Execution time Memory
768666 2023-06-28T10:53:52 Z milisav Wall (IOI14_wall) C++14
100 / 100
 724 ms 77412 KB 
#include<bits/stdc++.h>
#define maxn 2500000
using namespace std;

int p[4*maxn];
int q[4*maxn];
int a[maxn];

void updateLow(int id,int pi) {
    if(p[id]==q[id]) {
        p[id]=q[id]=max(p[id],pi);
    }
    else {
        p[id]=max(p[id],pi);
        if(p[id]>q[id]) q[id]=p[id];
    }
}

void updateHigh(int id,int qi) {
    if(p[id]==q[id]) {
        p[id]=q[id]=min(q[id],qi);
    }
    else {
        q[id]=min(q[id],qi);
        if(q[id]<p[id]) p[id]=q[id];
    }
}

void propagate(int id,int l,int r) {
    if(l!=r) {
        if(p[id]!=-1) {
            updateLow(id*2+1,p[id]);
            updateLow(id*2+2,p[id]);
        }
        if(q[id]!=1e9+1) {
            updateHigh(id*2+1,q[id]);
            updateHigh(id*2+2,q[id]);
        }
        p[id]=-1;
        q[id]=1e9+1;
    }
}

void prepare(int id,int l,int r) {
    propagate(id,l,r);
    if(l==r) {
        a[l]=max(a[l],p[id]);
        a[r]=min(a[r],q[id]);
        return;
    }
    int m=(l+r)/2;
    prepare(id*2+1,l,m);
    prepare(id*2+2,m+1,r);
}

void maxQuery(int id,int l,int r,int x,int y,int pi) {
    propagate(id,l,r);
    if(x<=l && r<=y) {
        updateLow(id,pi);
        return;
    }
    if(y<l || r<x) {
        return;
    }
    int m=(l+r)/2;
    maxQuery(id*2+1,l,m,x,y,pi);
    maxQuery(id*2+2,m+1,r,x,y,pi);
}

void minQuery(int id,int l,int r,int x,int y,int qi) {
    propagate(id,l,r);
    if(x<=l && r<=y) {
        updateHigh(id,qi);
        return;
    }
    if(y<l || r<x) {
        return;
    }
    int m=(l+r)/2;
    minQuery(id*2+1,l,m,x,y,qi);
    minQuery(id*2+2,m+1,r,x,y,qi);
}

void createSeg(int id,int l,int r) {
    p[id]=-1;
    q[id]=1e9+1;
    if(l==r) return;
    int m=(l+r)/2;
    createSeg(id*2+1,l,m);
    createSeg(id*2+2,m+1,r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    createSeg(0,0,n-1);
    for(int i=0;i<k;i++) {
        if(op[i]==1) maxQuery(0,0,n-1,left[i],right[i],height[i]);
        else minQuery(0,0,n-1,left[i],right[i],height[i]);
    }
    prepare(0,0,n-1);
    for(int i=0;i<n;i++) finalHeight[i]=a[i];
}

/*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 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 117 ms 8340 KB Output is correct
3 Correct 143 ms 8048 KB Output is correct
4 Correct 427 ms 20796 KB Output is correct
5 Correct 215 ms 21772 KB Output is correct
6 Correct 212 ms 20172 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 764 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 98 ms 13868 KB Output is correct
9 Correct 159 ms 8072 KB Output is correct
10 Correct 430 ms 20736 KB Output is correct
11 Correct 217 ms 21792 KB Output is correct
12 Correct 212 ms 20228 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 104 ms 13968 KB Output is correct
15 Correct 37 ms 2020 KB Output is correct
16 Correct 700 ms 21092 KB Output is correct
17 Correct 214 ms 20428 KB Output is correct
18 Correct 220 ms 20380 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 832 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 836 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 99 ms 13872 KB Output is correct
9 Correct 150 ms 8076 KB Output is correct
10 Correct 459 ms 20816 KB Output is correct
11 Correct 216 ms 21924 KB Output is correct
12 Correct 218 ms 20228 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 101 ms 14052 KB Output is correct
15 Correct 40 ms 2004 KB Output is correct
16 Correct 724 ms 20988 KB Output is correct
17 Correct 219 ms 20536 KB Output is correct
18 Correct 219 ms 20428 KB Output is correct
19 Correct 562 ms 77384 KB Output is correct
20 Correct 572 ms 74956 KB Output is correct
21 Correct 561 ms 77280 KB Output is correct
22 Correct 551 ms 74864 KB Output is correct
23 Correct 573 ms 74868 KB Output is correct
24 Correct 569 ms 74832 KB Output is correct
25 Correct 588 ms 74836 KB Output is correct
26 Correct 553 ms 77376 KB Output is correct
27 Correct 551 ms 77412 KB Output is correct
28 Correct 583 ms 74788 KB Output is correct
29 Correct 551 ms 74872 KB Output is correct
30 Correct 557 ms 74768 KB Output is correct