oj.uz

Submission #768663

# Submission time Handle Problem Language Result Execution time Memory
768663 2023-06-28T10:48:55 Z milisav Wall (IOI14_wall) C++14
0 / 100
 119 ms 13872 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]=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]=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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 119 ms 13872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 2 ms 448 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -