Submission #1229550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229550		ivaziva	Wall (IOI14_wall)	C++20	0 / 100	155 ms	327680 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

#define MAXN 2000001

struct Segtree{
    int sum;int maksi,mini;
    int drugimaksi,drugimini;
    int brojmaksi,brojmini;
};

Segtree seg[MAXN*4];

Segtree mergee(Segtree seg1,Segtree seg2)
{
    Segtree ans;ans.sum=seg1.sum+seg2.sum;
    if (seg1.maksi==seg2.maksi) {ans.maksi=seg1.maksi;ans.drugimaksi=max(seg1.drugimaksi,seg2.drugimaksi);ans.brojmaksi=seg1.brojmaksi+seg2.brojmaksi;}
    else if (seg1.maksi>seg2.maksi) {ans.maksi=seg1.maksi;ans.drugimaksi=max(seg1.drugimaksi,seg2.maksi);ans.brojmaksi=seg1.brojmaksi;}
    else {ans.maksi=seg2.maksi;ans.drugimaksi=max(seg1.maksi,seg2.drugimaksi);ans.brojmaksi=seg2.brojmaksi;}
    if (seg1.mini==seg2.mini) {ans.mini=seg1.mini;ans.drugimini=min(seg1.drugimini,seg2.drugimini);ans.brojmini=seg1.brojmini+seg2.brojmini;}
    else if (seg1.mini<seg2.mini) {ans.mini=seg1.mini;ans.drugimini=min(seg1.drugimini,seg2.mini);ans.brojmini=seg1.brojmini;}
    else {ans.mini=seg2.mini;ans.drugimini=min(seg1.mini,seg2.drugimini);ans.brojmini=seg2.brojmini;}
    return ans;
}

void build(int node,int l,int r)
{
    if (l==r) seg[node]={0,0,0,-INT_MAX,INT_MAX,1,1};
    else {int mid=(l+r)/2;build(2*node,l,mid);build(2*node+1,mid+1,r);seg[node]=mergee(seg[2*node],seg[2*node+1]);}
}

void pushmin(int node,int l,int r,int x)
{
    if (seg[node].maksi<=x) return;
    seg[node].sum+=(long long)seg[node].brojmaksi*(x-seg[node].maksi);seg[node].maksi=x;
    if (seg[node].mini>x) seg[node].mini=x;
    if (l!=r) {int mid=(l+r)/2;pushmin(2*node,l,mid,x);pushmin(2*node+1,mid+1,r,x);}
}

void pushmax(int node,int l,int r,int x)
{
    if (seg[node].mini>=x) return;
    seg[node].sum+=(long long)seg[node].brojmini*(x-seg[node].mini);seg[node].mini=x;
    if (seg[node].maksi<x) seg[node].maksi=x;
    if (l!=r) {int mid=(l+r)/2;pushmax(2*node,l,mid,x);pushmax(2*node+1,mid+1,r,x);}
}

void updatemin(int node,int l,int r,int a,int b,int x)
{
    if (a>b or seg[node].maksi<=x) return;
    if (l==a and r==b and seg[node].drugimaksi<x) {pushmin(node,l,r,x);return;}
    int mid=(l+r)/2;updatemin(2*node,l,mid,a,min(b,mid),x);updatemin(2*node+1,mid+1,r,max(a,mid+1),b,x);
    seg[node]=mergee(seg[2*node],seg[2*node+1]);
}

void updatemax(int node,int l,int r,int a,int b,int x)
{
    if (a>b or seg[node].mini>=x) return;
    if (l==a and r==b and seg[node].drugimini>x) {pushmax(node,l,r,x);return;}
    int mid=(l+r)/2;updatemax(2*node,l,mid,a,min(b,mid),x);updatemax(2*node+1,mid+1,r,max(a,mid+1),b,x);
    seg[node]=mergee(seg[2*node],seg[2*node+1]);
}

int query(int node,int l,int r,int a,int b)
{
    if (a>b) return 0;
    if (l==a and r==b) return seg[node].sum;
    int mid=(l+r)/2;return query(2*node,l,mid,a,min(b,mid))+query(2*node+1,mid+1,r,max(a,mid+1),b);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    build(1,1,n);
    for (int i=0;i<k;i++) 
    {
        if (op[i]==1) updatemax(1,1,n,left[i]+1,right[i]+1,height[i]);
        else updatemin(1,1,n,left[i]+1,right[i]+1,height[i]);
    }
    for (int i=0;i<n;i++) finalHeight[i]=query(1,1,n,i,i);
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39