제출 #98770

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98770		JustasZ	벽 (IOI14_wall)	C++14	0 / 100	510 ms	17420 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn = 1e5 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, k, done[maxn * 4], seg[maxn * 4];
pii lazy[maxn * 4];
void upd(int id, pii val)
{
    bool need = false;
    if(lazy[id].x == +1 && val.x == +1 && val.y > lazy[id].y) need = true;
    if(lazy[id].x == -1 && val.x == -1 && val.y < lazy[id].y) need = true;
    if(lazy[id].x != val.x) need = true;
    if(!need) return;
    if(val.x == -1) seg[id] = min(seg[id], val.y);
    else seg[id] = max(seg[id], val.y);
    lazy[id] = val;
    done[id] = 0;
}
void shift(int id)
{
    if(!done[id])
    {
        upd(id * 2, lazy[id]);
        upd(id * 2 + 1, lazy[id]);
        done[id] = 1;
    }
}
void modify(int x, int y, pii val, int id = 1, int l = 0, int r = n - 1)
{
    if(l > y || r < x) return;
    if(l >= x && r <= y)
    {
        upd(id, val);
        return;
    }
    shift(id);
    int mid = (l + r) / 2;
    modify(x, y, val, id * 2, l, mid);
    modify(x, y, val, id * 2 + 1, mid + 1, r);
}
vector<int>res;
void get(int id = 1, int l = 0, int r = n - 1)
{
    if(l == r)
    {
        res.pb(seg[id]);
        return;
    }
    shift(id);
    int mid = (l + r) / 2;
    get(id * 2, l, mid);
    get(id * 2 + 1, mid + 1, r);
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for(int i = 0; i < maxn * 4; i++) done[i] = 1;
    n = N, k = K;
    for(int i = 0; i < k; i++)
    {
        if(op[i] == 2) op[i] = -1;
        modify(left[i], right[i], pii(op[i], height[i]));
    }
    get();
    for(int i = 0; i < n; i++)
        finalHeight[i] = res[i];
    /*for(int i = 0; i < n; i++)
        cout << res[i] << " ";
    cout << endl;*/
}
/*int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    int op[] = {1, 2, 2, 1, 1, 2};
    int left[] = {1, 4, 3, 0, 2, 6};
    int right[] = {8, 9, 6, 5, 2, 7};
    int height[] = {4, 1, 5, 3, 5, 0};
    int finalHeight[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    buildWall(10, 6, op, left, right, height, finalHeight);
    return 0;
}*/

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