Submission #768666

#	Time	Username	Problem	Language	Result	Execution time	Memory
768666		milisav	Wall (IOI14_wall)	C++14	100 / 100	724 ms	77412 KiB

wall

#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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39