oj.uz

Submission #98770

# Submission time Handle Problem Language Result Execution time Memory
98770 2019-02-25T19:24:59 Z JustasZ Wall (IOI14_wall) C++14
0 / 100
 510 ms 17420 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1920 KB Output is correct
2 Correct 5 ms 2048 KB Output is correct
3 Incorrect 5 ms 1920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1920 KB Output is correct
2 Correct 160 ms 13176 KB Output is correct
3 Correct 143 ms 9720 KB Output is correct
4 Incorrect 510 ms 17420 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1920 KB Output is correct
2 Correct 5 ms 2048 KB Output is correct
3 Incorrect 5 ms 1920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1920 KB Output is correct
2 Correct 6 ms 2020 KB Output is correct
3 Incorrect 5 ms 2020 KB Output isn't correct
4 Halted 0 ms 0 KB -