oj.uz

Submission #625238

# Submission time Handle Problem Language Result Execution time Memory
625238 2022-08-09T16:45:26 Z kakayoshi Wall (IOI14_wall) C++17
100 / 100
 1232 ms 159544 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define forw(i,a,b) for(int i=a;i<=b;i++)
#define forb(i,a,b) for(int i=a;i>=b;i--)
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define getbit(mask,i) ((mask>>i)&1)
typedef long long int ll;
typedef pair<int,int> pii;
const ll maxN=2e6+5;
const ll mod=1e9+7;
const ll oo=1e9;
int ans[maxN];
struct segment
{
    vector <int> mi,ma;
    vector <pair<int,int>> lazy;
    segment(int n)
    {
        mi.assign(4*n+5,oo);
        ma.assign(4*n+5,-oo);
        lazy.assign(4*n+5,{-oo,oo});
    }
    void maxi(int id, int h)
    {
        ma[id]=max(ma[id],h);
        mi[id]=max(ma[id],h);
        lazy[id].fi=max(lazy[id].fi,h);
        lazy[id].se=max(lazy[id].se,h);
        return;
    }
    void mini(int id, int h)
    {
        ma[id]=min(ma[id],h);
        mi[id]=min(mi[id],h);
        lazy[id].fi=min(lazy[id].fi,h);
        lazy[id].se=min(lazy[id].se,h);
        return;
    }
    void down(int id)
    {
        maxi(id*2,lazy[id].fi);
        maxi(id*2+1,lazy[id].fi);
        mini(id*2,lazy[id].se);
        mini(id*2+1,lazy[id].se);
        lazy[id]={-oo,+oo};
        return;
    }
    void update(int id, int l, int r,int u, int v, int type, int h) // 1 : add, 2: remove
    {
        if (v<l || r<u) return;
        if (u<=l && r<=v)
        {
            if (type==1) maxi(id,h);
            else mini(id,h);
            return;
        }
        down(id);
        int mid=(l+r)/2;
        update(id*2,l,mid,u,v,type,h);
        update(id*2+1,mid+1,r,u,v,type,h);
        ma[id]=ma[id*2];
        mi[id]=mi[id*2];
        maxi(id,ma[id*2+1]);
        mini(id,mi[id*2+1]);
        lazy[id]={-oo,oo};
        return;
    }
    void get_ans(int id, int l, int r)
    {
        if (l==r)
        {
            if (ma[id]==-oo) ans[l]=0;
            else ans[l]=ma[id];
            return;
        }
        down(id);
        int mid=(l+r)/2;
        get_ans(id*2,l,mid);
        get_ans(id*2+1,mid+1,r);
        return;
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    segment seg(n);
    forw(i,0,k-1)
        seg.update(1,1,n,left[i]+1,right[i]+1,op[i],height[i]);
    seg.get_ans(1,1,n);
    forw(i,0,n-1)
        finalHeight[i]=ans[i+1];
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 10 ms 1112 KB Output is correct
5 Correct 7 ms 1088 KB Output is correct
6 Correct 8 ms 1088 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 165 ms 10396 KB Output is correct
3 Correct 286 ms 6040 KB Output is correct
4 Correct 824 ms 17360 KB Output is correct
5 Correct 467 ms 16088 KB Output is correct
6 Correct 462 ms 16080 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 2 ms 448 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 8 ms 1108 KB Output is correct
5 Correct 7 ms 1108 KB Output is correct
6 Correct 7 ms 1148 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 135 ms 9296 KB Output is correct
9 Correct 282 ms 6044 KB Output is correct
10 Correct 854 ms 16460 KB Output is correct
11 Correct 461 ms 16212 KB Output is correct
12 Correct 457 ms 16220 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 174 ms 9172 KB Output is correct
15 Correct 44 ms 2460 KB Output is correct
16 Correct 869 ms 16280 KB Output is correct
17 Correct 501 ms 16332 KB Output is correct
18 Correct 516 ms 16220 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 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 9 ms 1108 KB Output is correct
5 Correct 8 ms 1084 KB Output is correct
6 Correct 7 ms 1152 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 142 ms 9288 KB Output is correct
9 Correct 278 ms 6092 KB Output is correct
10 Correct 772 ms 16564 KB Output is correct
11 Correct 482 ms 16208 KB Output is correct
12 Correct 503 ms 16328 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 129 ms 9276 KB Output is correct
15 Correct 44 ms 2448 KB Output is correct
16 Correct 854 ms 16276 KB Output is correct
17 Correct 493 ms 16220 KB Output is correct
18 Correct 484 ms 16128 KB Output is correct
19 Correct 1187 ms 159436 KB Output is correct
20 Correct 1154 ms 159436 KB Output is correct
21 Correct 1140 ms 159440 KB Output is correct
22 Correct 1154 ms 159436 KB Output is correct
23 Correct 1157 ms 159436 KB Output is correct
24 Correct 1150 ms 159544 KB Output is correct
25 Correct 1232 ms 159444 KB Output is correct
26 Correct 1202 ms 159440 KB Output is correct
27 Correct 1166 ms 159448 KB Output is correct
28 Correct 1185 ms 159472 KB Output is correct
29 Correct 1168 ms 159428 KB Output is correct
30 Correct 1138 ms 159444 KB Output is correct