oj.uz

Submission #388440

# Submission time Handle Problem Language Result Execution time Memory
388440 2021-04-11T14:21:03 Z ACmachine Wall (IOI14_wall) C++17
100 / 100
 1177 ms 74208 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)

const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;

template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "[";  REP(i, U) out << v[i] << ", ";  out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}

template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
// on segtree[TIME] is operation information
// I toggle operations as I scanline

int n, k;
vector<int> op, height;
struct node{
    bool Sop = false;
    int S = -1, D = INF, I = -1;
    void apply(int _D, int _I){
        Sop = false; D = _D; I = _I;
    }
};
struct segtree{
    node comb(const node& a, const node& b){
        node res;
        if(b.Sop){res = b; return res;}
        res = a; // will be overwritten
        if(res.Sop){
            res.S = max(res.S, b.I);
            res.S = min(res.S, b.D);
            return res;
        }
        res.I = max(res.I, b.I);
        res.D = min(res.D, b.D);
        if(res.D <= res.I){
            res.Sop = true;
            res.S = ((res.I == b.I) ? res.I : res.D);
        }
        return res;
    }
    int n;
    vector<node> tree;
    segtree(int _n){
        n = 1; while(n < _n) n*= 2;
        tree.resize(2 * n);
    }
    void upd(int pos, int state){
        int _D, _I;
        if(state == 1){
            if(op[pos] == 1){_I = height[pos]; _D = INF;}
            else{_I = -1; _D = height[pos];}
        }
        else{
            _D = INF;
            _I = -1;
        }
        pos += n;
        tree[pos].apply(_D, _I);
        for(int i = pos / 2; i > 0; i/=2)
            tree[i] = comb(tree[i<<1], tree[i<<1|1]);
    }
    int query(int value){ //what it gets transformed to
        if(tree[1].Sop)
            return tree[1].S;
        value = max(value, tree[1].I);
        value = min(value, tree[1].D);
        return value;
    }
};

void buildWall(int N, int K, int OP[], int LEFT[], int RIGHT[], int HEIGHT[], int finalHeight[]){
    n = N; k = K;
    op.resize(K); height.resize(K);
    REP(i, k){
        op[i] = OP[i]; height[i] = HEIGHT[i];
    }
    segtree st(k);
    vector<array<int, 2>> ev(k);
    REP(i, k) ev[i] = {LEFT[i], i};
    sort(all(ev));
    int pp = 0;
    set<pair<int, int>> open;
    REP(i, n){
        while(pp < ev.size() && ev[pp][0] <= i){
            st.upd(ev[pp][1], 1);
            open.insert({RIGHT[ev[pp][1]], ev[pp][1]});
            pp++;
        }
        while(!open.empty() && open.begin()->ff < i){
            st.upd(open.begin()->ss, 0);
            open.erase(open.begin());
        }
        finalHeight[i] = st.query(0);
    }
    return;
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:130:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         while(pp < ev.size() && ev[pp][0] <= i){
      |               ~~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 4 ms 972 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 8 ms 872 KB Output is correct
5 Correct 6 ms 972 KB Output is correct
6 Correct 6 ms 972 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 396 ms 61576 KB Output is correct
3 Correct 383 ms 23748 KB Output is correct
4 Correct 1173 ms 54264 KB Output is correct
5 Correct 470 ms 44608 KB Output is correct
6 Correct 469 ms 43284 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 4 ms 956 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 6 ms 928 KB Output is correct
5 Correct 6 ms 1000 KB Output is correct
6 Correct 6 ms 972 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 388 ms 61784 KB Output is correct
9 Correct 365 ms 23620 KB Output is correct
10 Correct 1177 ms 54280 KB Output is correct
11 Correct 466 ms 44740 KB Output is correct
12 Correct 479 ms 43196 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 409 ms 61684 KB Output is correct
15 Correct 35 ms 3636 KB Output is correct
16 Correct 1126 ms 54160 KB Output is correct
17 Correct 476 ms 43616 KB Output is correct
18 Correct 494 ms 43636 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 4 ms 972 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 6 ms 844 KB Output is correct
5 Correct 6 ms 1012 KB Output is correct
6 Correct 6 ms 972 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 395 ms 61680 KB Output is correct
9 Correct 394 ms 23756 KB Output is correct
10 Correct 1162 ms 54204 KB Output is correct
11 Correct 468 ms 44792 KB Output is correct
12 Correct 469 ms 43300 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 389 ms 61788 KB Output is correct
15 Correct 36 ms 3652 KB Output is correct
16 Correct 1066 ms 54224 KB Output is correct
17 Correct 537 ms 43608 KB Output is correct
18 Correct 473 ms 43792 KB Output is correct
19 Correct 698 ms 74176 KB Output is correct
20 Correct 708 ms 74188 KB Output is correct
21 Correct 735 ms 74124 KB Output is correct
22 Correct 696 ms 74092 KB Output is correct
23 Correct 680 ms 74068 KB Output is correct
24 Correct 693 ms 74084 KB Output is correct
25 Correct 690 ms 74208 KB Output is correct
26 Correct 709 ms 74044 KB Output is correct
27 Correct 693 ms 74092 KB Output is correct
28 Correct 682 ms 74180 KB Output is correct
29 Correct 682 ms 74052 KB Output is correct
30 Correct 690 ms 74036 KB Output is correct