oj.uz

Submission #1008563

# Submission time Handle Problem Language Result Execution time Memory
1008563 2024-06-26T14:26:16 Z hotboy2703 Wall (IOI14_wall) C++14
100 / 100
 436 ms 64656 KB 
#include "wall.h"

#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 5e5+100;
const ll INF = 1e9;
ll n,k;
namespace segtree{
    pll tree[MAXN*4];
    void build(ll id,ll l,ll r){
        tree[id] = MP(0,INF);
        if (l != r){
            ll mid = (l + r) >> 1;
            build(id<<1,l,mid);
            build(id<<1|1,mid+1,r);
        }
    }
    void update(ll id,ll l,ll r,ll i,pll v){
        if (l > i || r < i)return;
        if (l==r){
            tree[id] = v;
            return;
        }
        ll mid = (l + r) >> 1;
        update(id<<1,l,mid,i,v);
        update(id<<1|1,mid+1,r,i,v);
        if (tree[id<<1].fi > tree[id<<1|1].se){
            tree[id] = MP(tree[id<<1|1].se,tree[id<<1|1].se);
        }
        else if (tree[id<<1|1].fi > tree[id<<1].se){
            tree[id] = MP(tree[id<<1|1].fi,tree[id<<1|1].fi);
        }
        else{
            tree[id].fi = max(tree[id<<1].fi,tree[id<<1|1].fi);
            tree[id].se = min(tree[id<<1].se,tree[id<<1|1].se);
        }
//        cout<<"SUS "<<id<<' '<<l<<' '<<r<<' '<<tree[id].fi<<' '<<tree[id].se<<'\n';
    }
    void update(ll i,pll v){
//        cout<<i<<' '<<v.fi<<' '<<v.se<<'\n';
        update(1,1,k,i,v);
    }
}
struct query{
    ll time,type,h,x,ins;
};
vector <query> all;

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
    n=N,k=K;
    for (ll i = 0;i < k;i ++){
        all.push_back({i+1,op[i],height[i],left[i],true});
        all.push_back({i+1,op[i],height[i],right[i]+1,false});
    }
    sort(all.begin(),all.end(),[&](query a,query b){return a.x < b.x;});
//    cout<<"SUS "<<all[0].x<<endl;
    using namespace segtree;
    build(1,1,k);
    for (ll i = 0,ptr = 0;i < n;i ++){
        while (ptr<sz(all) && all[ptr].x==i){
            query tmp = all[ptr];
            if (tmp.ins){
                pll rg;
                if (tmp.type==1)rg = MP(tmp.h,INF);
                else rg = MP(0,tmp.h);
                update(tmp.time,rg);
            }
            else{
                update(tmp.time,MP(0,INF));
            }
            ptr++;
        }
//        cout<<i<<' '<<tree[1].fi<<'\n';
        finalHeight[i] = tree[1].fi;
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 920 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 4 ms 964 KB Output is correct
6 Correct 4 ms 968 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 185 ms 41928 KB Output is correct
3 Correct 149 ms 19780 KB Output is correct
4 Correct 415 ms 46228 KB Output is correct
5 Correct 294 ms 47248 KB Output is correct
6 Correct 292 ms 45688 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 920 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 4 ms 1088 KB Output is correct
5 Correct 4 ms 1088 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 203 ms 41936 KB Output is correct
9 Correct 135 ms 19912 KB Output is correct
10 Correct 343 ms 46380 KB Output is correct
11 Correct 294 ms 47248 KB Output is correct
12 Correct 325 ms 45772 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 234 ms 41872 KB Output is correct
15 Correct 23 ms 3276 KB Output is correct
16 Correct 397 ms 46484 KB Output is correct
17 Correct 323 ms 45852 KB Output is correct
18 Correct 345 ms 46016 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 920 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 8 ms 1088 KB Output is correct
5 Correct 3 ms 1088 KB Output is correct
6 Correct 4 ms 1088 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 187 ms 42092 KB Output is correct
9 Correct 140 ms 19732 KB Output is correct
10 Correct 416 ms 46224 KB Output is correct
11 Correct 301 ms 47248 KB Output is correct
12 Correct 314 ms 45712 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 203 ms 41832 KB Output is correct
15 Correct 26 ms 3280 KB Output is correct
16 Correct 421 ms 46480 KB Output is correct
17 Correct 332 ms 45972 KB Output is correct
18 Correct 327 ms 45976 KB Output is correct
19 Correct 407 ms 64588 KB Output is correct
20 Correct 391 ms 62348 KB Output is correct
21 Correct 413 ms 64656 KB Output is correct
22 Correct 429 ms 62096 KB Output is correct
23 Correct 380 ms 62352 KB Output is correct
24 Correct 398 ms 62096 KB Output is correct
25 Correct 391 ms 62096 KB Output is correct
26 Correct 406 ms 64492 KB Output is correct
27 Correct 393 ms 64596 KB Output is correct
28 Correct 419 ms 62100 KB Output is correct
29 Correct 436 ms 62104 KB Output is correct
30 Correct 402 ms 62096 KB Output is correct