Submission #617847

#	Time	Username	Problem	Language	Result	Execution time	Memory
617847		beedle	Wall (IOI14_wall)	C++17	100 / 100	783 ms	161948 KiB

wall

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