Submission #163409

#	Time	Username	Problem	Language	Result	Execution time	Memory
163409		davitmarg	Wall (IOI14_wall)	C++17	0 / 100	3010 ms	18460 KiB

wall

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

#ifndef death
#include "wall.h"
#endif

const int N = 2000006;

pair<LL, LL> t[4 * N], d[4 * N];
int col[4 * N], dcol[4 * N];

void build(int v, int l, int r)
{
    d[v] = MP(-1, -1);
    col[v] = 1;
    t[v] = MP(0, mod * mod);
    if (l == r)
        return;
    int m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
}

void pushColor(int v, int l, int r, int f = 1)
{
    if (dcol[v] == 0)
        return;
    if (l != r)
    {
        dcol[v * 2] = dcol[v];
        dcol[v * 2 + 1] = dcol[v];
        if (f)
        {
            int m = (l + r) / 2;
            pushColor(v * 2, l, m, 0);
            pushColor(v * 2 + 1, m + 1, r, 0);
        }
    }
    col[v] = dcol[v];
    dcol[v] = 0;
}

void paint(int v, int l, int r, int i, int j, int c)
{
    pushColor(v, l, r);
    if (i > j)
        return;
    if (l == i && r == j)
    {
        dcol[v] = c;
        pushColor(v, l, r);
        return;
    }
    int m = (l + r) / 2;
    paint(v * 2, l, m, i, min(j, m), c);
    paint(v * 2 + 1, m + 1, r, max(i, m + 1), j, c);
}

int getCol(int v, int l, int r, int pos)
{
    pushColor(v, l, r);
    if (l == r)
        return col[v];
    int m = (l + r) / 2;
    if (pos <= m)
        return getCol(v * 2, l, m, pos);
    else
        return getCol(v * 2 + 1, m + 1, r, pos);
}

void addLazy(pair<LL, LL> &a, pair<LL, LL> b)
{
    if (b.first != -1)
        if (a.first == -1)
            a.first = b.first;
        else
            a.first = max(b.first, a.first);

    if (b.second != -1)
        if (a.second == -1)
            a.second = b.second;
        else
            a.second = min(b.second, a.second);
}

pair<LL, LL> merge(pair<LL, LL> a, pair<LL, LL> b)
{
    a.first = min(a.first, b.first);
    a.second = max(a.second, b.second);
    return a;
}

void push(int v, int l, int r, int f = 1)
{
    if (l != r)
    {
        if (f)
        {
            int m = (l + r) / 2;
            push(v * 2, l, m, 0);
            push(v * 2 + 1, m + 1, r, 0);
        }
        addLazy(d[v * 2], d[v]);
        addLazy(d[v * 2 + 1], d[v]);
        if (f)
        {
            int m = (l + r) / 2;
            push(v * 2, l, m, 0);
            push(v * 2 + 1, m + 1, r, 0);
        }
    }
    if (d[v].first != -1)
    {
        t[v].first = max(t[v].first, d[v].first);
        t[v].second = max(t[v].second, t[v].first);
    }
    if (d[v].second != -1)
    {
        t[v].second = min(t[v].second, d[v].second);
        t[v].first = min(t[v].second, t[v].first);
    }
    d[v].first = d[v].second = -1;
}

void add(int v, int l, int r, int i, int j, pair<LL, LL> val)
{
    push(v, l, r);
    if (i > j)
        return;
    if (l == i && r == j)
    {
        addLazy(d[v], val);
        //cout << d[v].first << " : " << d[v].second << endl;
        push(v, l, r);
        return;
    }
    int m = (l + r) / 2;
    add(v * 2, l, m, i, min(j, m), val);
    add(v * 2 + 1, m + 1, r, max(i, m + 1), j, val);
    t[v] = merge(t[v * 2], t[v * 2 + 1]);
}

pair<LL, LL> get(int v, int l, int r, int i, int j)
{
    push(v, l, r);
    if (i > j)
        return MP(mod * mod, -mod * mod);
    if (l == i && r == j)
        return t[v];
    int m = (l + r) / 2;
    return merge(
        get(v * 2, l, m, i, min(j, m)),
        get(v * 2 + 1, m + 1, r, max(i, m + 1), j));
}

void buildWall(int n, int k, int op[], int L[], int R[], int H[], int fin[])
{
    build(1, 0, n - 1);
    for (int i = 0; i < k; i++)
    {
        if (op[i] == 1)
            add(1, 0, n - 1, L[i], R[i], MP(H[i], mod * mod));
        else
            add(1, 0, n - 1, L[i], R[i], MP(0, H[i]));
        paint(1, 0, n - 1, L[i], R[i], op[i]);
    }
    for (int i = 0; i < n; i++)
    {
        pair<LL, LL> p = get(1, 0, n - 1, i, i);
        //cout << p.first << " : " << p.second << " | " << getCol(1, 0, n - 1, i) << endl;
        if (p.first <= p.second)
            fin[i] = p.first;
        else if (getCol(1, 0, n - 1, i) == 1)
            fin[i] = p.first;
        else
            fin[i] = p.second;
    }
}

#ifdef death

int main()
{
    int N, K, L[102], R[102], OP[102], H[102], A[102];
    cin >> N >> K;
    for (int i = 0; i < K; i++)
        cin >> OP[i] >> L[i] >> R[i] >> H[i];
    buildWall(N, K, OP, L, R, H, A);
    for (int i = 0; i < N; i++)
        cout << A[i] << endl;

    return 0;
}

#endif

/*

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

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

Compilation message (stderr)

wall.cpp: In function 'void addLazy(std::pair<long long int, long long int>&, std::pair<long long int, long long int>)':
wall.cpp:95:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
     if (b.first != -1)
        ^
wall.cpp:101:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
     if (b.second != -1)
        ^

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