oj.uz

Submission #617847

# Submission time Handle Problem Language Result Execution time Memory
617847 2022-08-01T15:23:18 Z beedle Wall (IOI14_wall) C++17
100 / 100
 783 ms 161948 KB 
#include "wall.h"
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <random>
#include <chrono>
#define pi 3.141592653589793238
#define ll long long
#define ld long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 1000000007ll
#define INF 1000000000000000000
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)
 
using namespace std;

pair <ll,ll> t[4*2000000+40];
 
pair <ll,ll> combine(pair <ll,ll> p1, pair <ll,ll> p2)
{
    if(p1.ss<p2.ff)
    return {p2.ff,p2.ff};
    else if (p1.ff>p2.ss)
    return {p2.ss,p2.ss};
    else return make_pair(max(p1.ff,p2.ff), min(p1.ss,p2.ss));
}
 
void push(int v)
{
    pair <ll,ll> p={-INF,INF};
    if(t[v]!=p)
    {
        t[2*v]=combine(t[2*v],t[v]);
        t[2*v+1]=combine(t[2*v+1],t[v]);
        t[v]={-INF,INF};
    }
}
 
void update(ll v, ll tl, ll tr, ll l, ll r, pair <ll,ll> add) {
    if (l > r)
        return;
    if (l == tl && r == tr) {
        t[v] = combine(t[v],add);
    } else {
        push(v);
        ll tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), add);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, add);
        //t[v]=combine(t[2*v],t[2*v+1]);
    }
}
 
 
pair<ll,ll> get(ll v, ll tl, ll tr, ll pos) {
    if (tl == tr)
        return t[v];
    ll tm = (tl + tr) / 2;
    if (pos <= tm)
        return combine(get(v*2, tl, tm, pos), t[v]);
    else
        return combine(get(v*2+1, tm+1, tr, pos),t[v]);
}

void buildWall(int n, int k, int Op[], int left[], int right[], int height[], int finalHeight[]){
  rep(i,0,4*2000000+40)
  t[i]={-INF,INF};
    
    rep(itr,0,k-1)
    {
        int op=Op[itr];
        
        if(op==1)
        {
            ll l=left[itr], r=right[itr], v=height[itr];
            pair <ll,ll> p=make_pair(v,INF);
            update(1,0,n-1,l,r,p);
        }
        else
        {
            ll l=left[itr], r=right[itr], v=height[itr];
            pair <ll,ll> p=make_pair(-INF,v);
            update(1,0,n-1,l,r,p);
        }
    }
    
    rep(i,0,n-1)
    {
        pair <ll,ll> p;
        p=get(1,0,n-1,i);
        if(0<p.ff)
        finalHeight[i]=p.ff;
        else if (0>=p.ff && 0<=p.ss)
        finalHeight[i]=0;
        else if (0>p.ss)
        finalHeight[i]=p.ss;
    }
    
    //cout<<endl<<endl<<t[1].ff<<" "<<t[1].ss<<endl<<t[2].ff<<" "<<t[2].ss<<endl<<t[3].ff<<" "<<t[3].ss;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 125452 KB Output is correct
2 Correct 55 ms 125628 KB Output is correct
3 Correct 51 ms 125584 KB Output is correct
4 Correct 59 ms 125772 KB Output is correct
5 Correct 57 ms 125680 KB Output is correct
6 Correct 62 ms 125772 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 125524 KB Output is correct
2 Correct 186 ms 139112 KB Output is correct
3 Correct 193 ms 132596 KB Output is correct
4 Correct 509 ms 143624 KB Output is correct
5 Correct 276 ms 144576 KB Output is correct
6 Correct 276 ms 143004 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125460 KB Output is correct
2 Correct 49 ms 125616 KB Output is correct
3 Correct 59 ms 125564 KB Output is correct
4 Correct 57 ms 125716 KB Output is correct
5 Correct 65 ms 125696 KB Output is correct
6 Correct 53 ms 125728 KB Output is correct
7 Correct 52 ms 125572 KB Output is correct
8 Correct 183 ms 139200 KB Output is correct
9 Correct 202 ms 132636 KB Output is correct
10 Correct 465 ms 143520 KB Output is correct
11 Correct 283 ms 144576 KB Output is correct
12 Correct 282 ms 142996 KB Output is correct
13 Correct 49 ms 125444 KB Output is correct
14 Correct 204 ms 139128 KB Output is correct
15 Correct 78 ms 126672 KB Output is correct
16 Correct 586 ms 143864 KB Output is correct
17 Correct 283 ms 143220 KB Output is correct
18 Correct 307 ms 143240 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 125548 KB Output is correct
2 Correct 50 ms 125616 KB Output is correct
3 Correct 51 ms 125480 KB Output is correct
4 Correct 58 ms 125704 KB Output is correct
5 Correct 61 ms 125756 KB Output is correct
6 Correct 56 ms 125736 KB Output is correct
7 Correct 51 ms 125460 KB Output is correct
8 Correct 192 ms 139180 KB Output is correct
9 Correct 202 ms 132640 KB Output is correct
10 Correct 470 ms 143520 KB Output is correct
11 Correct 287 ms 144544 KB Output is correct
12 Correct 277 ms 142956 KB Output is correct
13 Correct 56 ms 125516 KB Output is correct
14 Correct 194 ms 139188 KB Output is correct
15 Correct 81 ms 126728 KB Output is correct
16 Correct 611 ms 143772 KB Output is correct
17 Correct 295 ms 143168 KB Output is correct
18 Correct 305 ms 143156 KB Output is correct
19 Correct 733 ms 161872 KB Output is correct
20 Correct 728 ms 159360 KB Output is correct
21 Correct 758 ms 161892 KB Output is correct
22 Correct 719 ms 159460 KB Output is correct
23 Correct 720 ms 159356 KB Output is correct
24 Correct 719 ms 159492 KB Output is correct
25 Correct 747 ms 159332 KB Output is correct
26 Correct 783 ms 161844 KB Output is correct
27 Correct 743 ms 161948 KB Output is correct
28 Correct 722 ms 159340 KB Output is correct
29 Correct 714 ms 159392 KB Output is correct
30 Correct 743 ms 159452 KB Output is correct