oj.uz

답안 #1016587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1016587 2024-07-08T08:33:30 Z Ice_man 벽 (IOI14_wall) C++14
8 / 100
 140 ms 200160 KB 
/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include "wall.h"

#define maxn 2000005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

using namespace std;


typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;
typedef long double ld;


std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}



int lazy[maxn * 4];
pii tree[maxn * 4];


void push_lazy(int node, int l, int r)
{
    if(lazy[node] == -1)
        return;

    tree[node].X = lazy[node];
    tree[node].Y = lazy[node];

    if(l != r)
    {
        lazy[node * 2] = lazy[node];
        lazy[node * 2 + 1] = lazy[node];
    }

    lazy[node] = -1;
}


void _remove(int node, int l, int r, int ql, int qr, int qval)
{
    push_lazy(node, l, r);
    if(ql > r || qr < l)
        return;

    if(tree[node].Y <= qval)
        return;

    if(l >= ql && r <= qr && tree[node].X >= qval)
    {
        lazy[node] = qval;
        push_lazy(node, l, r);
        return;
    }

    int mid = (l + r) / 2;

    _remove(node * 2, l, mid, ql, qr, qval);
    _remove(node * 2 + 1, mid + 1, r, ql, qr, qval);

    tree[node].Y = max(tree[node * 2].Y , tree[node * 2 + 1].Y);
    tree[node].X = min(tree[node * 2].X , tree[node * 2 + 1].X);
}



void add(int node, int l, int r, int ql, int qr, int qval)
{
    push_lazy(node, l, r);
    if(ql > r || qr < l)
        return;

    if(tree[node].X >= qval)
        return;

    if(l >= ql && r <= qr && tree[node].Y <= qval)
    {
        lazy[node] = qval;
        push_lazy(node, l, r);
        return;
    }

    int mid = (l + r) / 2;

    add(node * 2, l, mid, ql, qr, qval);
    add(node * 2 + 1, mid + 1, r, ql, qr, qval);

    tree[node].Y = max(tree[node * 2].Y , tree[node * 2 + 1].Y);
    tree[node].X = min(tree[node * 2].X , tree[node * 2 + 1].X);
}


int ans[maxn];
void answer(int node , int l , int r)
{
    push_lazy(node , l , r);

    if(l == r)
    {
        ans[l - 1] = tree[node].X;
        return;
    }

    int mid = (l + r) / 2;

    answer(node * 2 , l , mid);
    answer(node * 2 + 1 , mid + 1 , r);
}


int pom[maxn];
void buildWall(int n , int k , int op[] , int left[] , int right[] , int height[] , int finalHeight[])
{
    n++;
    for(int i = 0; i < 4 * maxn; i++)
        lazy[i] = -1 , tree[i] = {0 , 0};

    for(int i = 0; i < k; i++)
        if(op[i] == 1)
            add(1 , 1 , n , left[i] + 1 , right[i] + 1 , height[i]);
        else
            _remove(1 , 1 , n , left[i] + 1 , right[i] + 1 , height[i]);

    answer(1 , 1 , n);
    for(int i = 0; i < n; i++)
        finalHeight[i] = ans[i];
}





/**int main()
{

#ifdef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ///startT = std::chrono::high_resolution_clock::now();

    add(1 , 1 , 10 , 2 , 9 , 4);
    _remove(1 , 1 , 10 , 5 , 10 , 1);
    _remove(1 , 1 , 10 , 4 , 7 , 5);
    add(1 , 1 , 10 , 1 , 6 , 3);
    add(1 , 1 , 10 , 3 , 3 , 5);
    _remove(1 , 1 , 10 , 7 , 8 , 0);

    answer(1 , 1 , 10);
    for(int i = 0; i < 10; i++)
        cout << ans[i] << " ";
    cout << endl;



    return 0;
}
*/

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 95312 KB Output is correct
2 Correct 20 ms 95324 KB Output is correct
3 Correct 19 ms 95428 KB Output is correct
4 Correct 27 ms 95572 KB Output is correct
5 Correct 22 ms 95576 KB Output is correct
6 Correct 21 ms 95580 KB Output is correct

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 95320 KB Output is correct
2 Correct 100 ms 103192 KB Output is correct
3 Runtime error 135 ms 200160 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 95320 KB Output is correct
2 Correct 20 ms 95456 KB Output is correct
3 Correct 19 ms 95320 KB Output is correct
4 Correct 24 ms 95580 KB Output is correct
5 Correct 22 ms 95576 KB Output is correct
6 Correct 23 ms 95576 KB Output is correct
7 Correct 23 ms 95316 KB Output is correct
8 Correct 102 ms 103080 KB Output is correct
9 Runtime error 140 ms 200020 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 95324 KB Output is correct
2 Correct 20 ms 95460 KB Output is correct
3 Correct 20 ms 95324 KB Output is correct
4 Correct 29 ms 95572 KB Output is correct
5 Correct 22 ms 95580 KB Output is correct
6 Correct 22 ms 95580 KB Output is correct
7 Correct 21 ms 95320 KB Output is correct
8 Correct 100 ms 103248 KB Output is correct
9 Runtime error 137 ms 199964 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -