Submission #600141

#	Time	Username	Problem	Language	Result	Execution time	Memory
600141		snokes	Wall (IOI14_wall)	C++17	0 / 100	868 ms	24208 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

#ifdef LOCAL
void print() {cerr << ']' << endl;}
template<typename Head, typename... Tail> void print(Head H, Tail... T) {cerr << ' ' << H; if(sizeof...(T)) cerr << ','; print(T...); }
template<typename T> ostream& operator << (ostream& os, vector<T> v){os << "["; bool first = 1; for(auto x : v) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator <<(ostream& os,pair<A, B> p) {return os << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename A, typename B, typename C> ostream& operator << (ostream& os, tuple<A, B, C> a) {os << '(' << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ")"; return os;}
template<typename A, size_t S> ostream& operator << (ostream& os, array<A, S> a) {os << "["; bool first = 1; for(auto x : a) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A> ostream& operator << (ostream& os, set<A> s) {os << "["; bool first = 1; for(auto x : s) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator << (ostream& os, map<A, B> m) {os << "["; bool first = 1; for(auto x : m) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
#define dbg(...) cerr << '[' << #__VA_ARGS__ << ":", print(__VA_ARGS__);
#else
#define dbg(...)
#endif // LOCAL

#define vt vector

const int INF = 1e9 + 5;

struct Op
{
    int mn, mx, mode;
    Op (int a, int b, int c)
    {
        mn = a;
        mx = b;
        mode = c;
    }
    void apply(const Op other)
    {
        assert(other.mode == 1 || other.mode == 2);
        if(mode == 0)
        {
            *this = other;
            return;
        }
        if(other.mode == 1)
        {
            //Min mode
            if(mode == 1) mn = min(mn, other.mn);
            else mn = min(mx, other.mn);
            mx = min(mx, mn);
        }
        else
        {
            //Max mode
            if(mode == 2) mx = max(mx, other.mx);
            else mx = max(other.mx, mn);
            mn = max(mn, mx);
        }
        mode = other.mode;
        assert(mn == mx);
    }
};

ostream& operator << (ostream& os, Op o)
{
    return os << "(mn:" << o.mn << ", mx: " << o.mx << ", mode:" << o.mode << ")";
}

bool operator == (Op a, Op b)
{
    return a.mn == b.mn && a.mx == b.mx && a.mode == b.mode;
}

const Op NONE(0, 0, 0);

struct SegTree
{
    vector<int> S;
    vector<Op> lazy;
    int N;

    SegTree(int _N)
    {
        for(N = 1; N < _N; N *= 2);
        S = vector<int>(2 * N);
        lazy = vector<Op>(2 * N, NONE);
    }

    void push(int i)
    {
        if(lazy[i] == NONE) return;
        assert(lazy[i].mn == lazy[i].mx);
        if(i < N) S[i] = lazy[i].mn;
        else
        {
            if(lazy[i].mode == 1) S[i] = min(S[i], lazy[i].mn);
            else S[i] = max(S[i], lazy[i].mx);
        }
        if(i < N)
        {
            lazy[2 * i].apply(lazy[i]);
            lazy[2 * i + 1].apply(lazy[i]);
        }
        lazy[i] = NONE;
    }

    int qry(int l, int r, int a, int b, int i)
    {
        push(i);
        if(l <= a && b <= r) return S[i];
        if(b < l || r < a) return 0;
        int m = (a + b) / 2;
        return qry(l, r, a, m, 2 * i) + qry(l, r, m + 1, b, 2 * i + 1);
    }
    int qry(int i)
    {
        assert(1 <= i && i <= N);
        return qry(i, i, 1, N, 1);
    }

    void upd(int l, int r, Op o, int a, int b, int i)
    {
        push(i);
        if(l <= a && b <= r)
        {
            dbg(o);
            lazy[i].apply(o);
            dbg(lazy[i]);
            push(i);
            return;
        }
        if(r < a || b < l) return;
        int m = (a + b) / 2;
        upd(l, r, o, a, m, 2 * i);
        upd(l, r, o, m + 1, b, 2 * i + 1);
    }
    void upd(int l, int r, Op o)
    {
        upd(l, r, o, 1, N, 1);
    }
};


void buildWall(int N, int Q, int op[], int left[], int right[], int height[], int finalHeight[])
{
    SegTree s(N);
    vector<pair<int, int>> range(2 * s.N);
    range[1] = {1, s.N};
    for(int i = 1; i < s.N; i++)
    {
        int m = (range[i].first + range[i].second) / 2;
        range[2 * i] = {range[i].first, m};
        range[2 * i + 1] = {m + 1, range[i].second};
    }
    //for(int i = 1; i <= N; i++) s.upd(i, i, Op(0, 0));
    for(int i = 0; i < Q; i++)
    {
        op[i] = op[i] == 1 ? 2 : 1;
        Op here(height[i], height[i], op[i]);
        //dbg(here);
        s.upd(1 + left[i], 1 + right[i], here);
        //for(int i = 1; i < 2 * s.N; i++) dbg(i, range[i], s.lazy[i]);
        //dbg("here");
    }

    for(int i = 0; i < N; i++)
    {
        finalHeight[i] = s.qry(i + 1);
    }
}

/*
int main()
{
  int n;
  int k;

  int i, j;
  int status = 0;

  status = scanf("%d%d", &n, &k);
  assert(status == 2);

  int* op = (int*)calloc(sizeof(int), k);
  int* left = (int*)calloc(sizeof(int), k);
  int* right = (int*)calloc(sizeof(int), k);
  int* height = (int*)calloc(sizeof(int), k);
  int* finalHeight = (int*)calloc(sizeof(int), n);

  for (i = 0; i < k; i++){
    status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
    assert(status == 4);
  }

  buildWall(n, k, op, left, right, height, finalHeight);

  for (j = 0; j < n; j++)
    printf("%d\n", finalHeight[j]);

  return 0;
}
*/

/*
6 2
1 3 4 3
2 3 5 1
*/

/*
10 2
1 3 4 2
2 3 5 1
*/

/*
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
*/

/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39