oj.uz

Submission #288708

# Submission time Handle Problem Language Result Execution time Memory
288708 2020-09-01T19:26:19 Z emil_physmath Wall (IOI14_wall) C++17
61 / 100
 3000 ms 42396 KB 
#include "wall.h"
#include <algorithm>
#include <iostream>
#include <random>
#include <chrono>
using namespace std;
using llong = long long;
#define BUGO(x) cerr << #x << " = " << (x) << '\n';
#define BUGOARR(a) {cerr << #a << ": "; for (auto i: a) cerr << i << ' '; cerr << '\n';}
#ifndef MANSON
#define BUGO(x)
#define BUGOARR(x)
#endif
ostream& operator<<(ostream& out, const pair<auto, auto>& p) {
	out << "{" << p.first << ", " << p.second << "}";
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
const int maxK = 500'005;
const int maxH = 100'000;

int mind[4 * maxK], maxu[4 * maxK];

void SetD(int v, int vl, int vr, int i, int x)
{
    if (vl == vr) {
        mind[v] = x;
        return;
    }
    int vm = vl + (vr - vl) / 2;
    if (i <= vm) SetD(v * 2, vl, vm, i, x);
    else SetD(v * 2 + 1, vm + 1, vr, i, x);
    mind[v] = min(mind[v * 2], mind[v * 2 + 1]);
}
int LastLess(int v, int vl, int vr, int x)
{
    if (vl == vr)
        return vr;
    int vm = vl + (vr - vl) / 2;
    if (mind[v * 2 + 1] >= x)
        return LastLess(v * 2, vl, vm, x);
    return LastLess(v * 2 + 1, vm + 1, vr, x);
}
void SetU(int v, int vl, int vr, int i, int x)
{
    if (vl == vr) {
        maxu[v] = x;
        return;
    }
    int vm = vl + (vr - vl) / 2;
    if (i <= vm) SetU(v * 2, vl, vm, i, x);
    else SetU(v * 2 + 1, vm + 1, vr, i, x);
    maxu[v] = max(maxu[v * 2], maxu[v * 2 + 1]);
}
int Max(int v, int vl, int vr, int l, int r) {
    if (l > vr || vl > r) return -1;
    if (l <= vl && vr <= r) return maxu[v];
    int vm = vl + (vr - vl) / 2;
    return max(Max(v * 2, vl, vm, l, r), Max(v * 2 + 1, vm + 1, vr, l, r));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int ans[])
{
    struct Upd {
        bool add;
        char dir;
        int time;
        int i, hei;
    };
    vector<Upd> upd;
    upd.reserve(2 * k + 5);
    upd.push_back({true, 'D', -1, -1, 0});
    for (int i = 0; i < k; ++i)
    {
        upd.push_back({true, op[i] == 1 ? 'U' : 'D', left[i], i, height[i]});
        upd.push_back({false, op[i] == 1 ? 'U' : 'D', right[i] + 1, i, height[i]});
    }
    sort(upd.begin(), upd.end(), [](const Upd& l, const Upd& r) {
         return l.time < r.time;
    });
    fill(mind, mind + k * 4, maxH + 1);
    fill(maxu, maxu + k * 4, -1);
    for (int i = 0, ind = 0; i < n; ++i)
    {
        while (ind < upd.size() && upd[ind].time <= i)
        {
            Upd& u = upd[ind];
            if (u.dir == 'D')
            {
                if (u.add)
                    SetD(1, -1, k - 1, u.i, u.hei);
                else
                    SetD(1, -1, k - 1, u.i, maxH + 1);
            }
            else
            {
                if (u.add)
                    SetU(1, 0, k - 1, u.i, u.hei);
                else
                    SetU(1, 0, k - 1, u.i, -1);
            }
            ++ind;
        }
        ans[i] = 0;
        int lans = 1, rans = maxH;
        while (lans <= rans)
        {
            int cans = (lans + rans) / 2;
            int l = LastLess(1, -1, k - 1, cans);
            if (l + 1 <= k - 1 && Max(1, 0, k - 1, l + 1, k - 1) >= cans) {
                ans[i] = cans;
                lans = cans + 1;
            }
            else
                rans = cans - 1;
        }
    }
}

Compilation message

wall.cpp:11: warning: "BUGO" redefined
   11 | #define BUGO(x)
      | 
wall.cpp:8: note: this is the location of the previous definition
    8 | #define BUGO(x) cerr << #x << " = " << (x) << '\n';
      | 
wall.cpp:12: warning: "BUGOARR" redefined
   12 | #define BUGOARR(x)
      | 
wall.cpp:9: note: this is the location of the previous definition
    9 | #define BUGOARR(a) {cerr << #a << ": "; for (auto i: a) cerr << i << ' '; cerr << '\n';}
      | 
wall.cpp:14:46: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   14 | ostream& operator<<(ostream& out, const pair<auto, auto>& p) {
      |                                              ^~~~
wall.cpp:14:52: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   14 | ostream& operator<<(ostream& out, const pair<auto, auto>& p) {
      |                                                    ^~~~
wall.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::pair<_T1, _T2>&)':
wall.cpp:16:1: warning: no return statement in function returning non-void [-Wreturn-type]
   16 | }
      | ^
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<buildWall(int, int, int*, int*, int*, int*, int*)::Upd>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         while (ind < upd.size() && upd[ind].time <= i)
      |                ~~~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 26 ms 896 KB Output is correct
5 Correct 28 ms 768 KB Output is correct
6 Correct 29 ms 768 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 331 ms 39640 KB Output is correct
3 Correct 292 ms 16688 KB Output is correct
4 Correct 985 ms 39980 KB Output is correct
5 Correct 573 ms 39928 KB Output is correct
6 Correct 555 ms 39816 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 26 ms 768 KB Output is correct
5 Correct 30 ms 768 KB Output is correct
6 Correct 29 ms 768 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 338 ms 39416 KB Output is correct
9 Correct 304 ms 16632 KB Output is correct
10 Correct 1043 ms 39900 KB Output is correct
11 Correct 615 ms 39800 KB Output is correct
12 Correct 584 ms 39800 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 361 ms 39676 KB Output is correct
15 Correct 73 ms 2816 KB Output is correct
16 Correct 1104 ms 40008 KB Output is correct
17 Correct 905 ms 39884 KB Output is correct
18 Correct 908 ms 39848 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 30 ms 768 KB Output is correct
5 Correct 30 ms 768 KB Output is correct
6 Correct 34 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 357 ms 39544 KB Output is correct
9 Correct 317 ms 16688 KB Output is correct
10 Correct 1031 ms 39912 KB Output is correct
11 Correct 605 ms 39892 KB Output is correct
12 Correct 578 ms 39800 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 339 ms 39544 KB Output is correct
15 Correct 83 ms 2816 KB Output is correct
16 Correct 1039 ms 40184 KB Output is correct
17 Correct 876 ms 40056 KB Output is correct
18 Correct 874 ms 39928 KB Output is correct
19 Execution timed out 3011 ms 42396 KB Time limit exceeded
20 Halted 0 ms 0 KB -