oj.uz

Submission #288701

# Submission time Handle Problem Language Result Execution time Memory
288701 2020-09-01T19:13:53 Z emil_physmath Wall (IOI14_wall) C++17
61 / 100
 3000 ms 45304 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.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;
    });
    for (int i = -1; i < k; ++i)
        SetD(1, -1, k - 1, i, maxH + 1);
    for (int i = 0; i < k; ++i)
        SetU(1, 0, k - 1, i, -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:85: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]
   85 |         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 5 ms 768 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 29 ms 896 KB Output is correct
5 Correct 30 ms 896 KB Output is correct
6 Correct 30 ms 896 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 477 ms 32228 KB Output is correct
3 Correct 358 ms 18260 KB Output is correct
4 Correct 1143 ms 42204 KB Output is correct
5 Correct 714 ms 42820 KB Output is correct
6 Correct 708 ms 41280 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 27 ms 896 KB Output is correct
5 Correct 30 ms 896 KB Output is correct
6 Correct 32 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 477 ms 32176 KB Output is correct
9 Correct 361 ms 18260 KB Output is correct
10 Correct 1134 ms 42304 KB Output is correct
11 Correct 712 ms 42816 KB Output is correct
12 Correct 708 ms 41280 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 490 ms 37952 KB Output is correct
15 Correct 82 ms 3052 KB Output is correct
16 Correct 1177 ms 42304 KB Output is correct
17 Correct 1049 ms 41860 KB Output is correct
18 Correct 1030 ms 41608 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 4 ms 800 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 28 ms 896 KB Output is correct
5 Correct 30 ms 896 KB Output is correct
6 Correct 30 ms 896 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 477 ms 32196 KB Output is correct
9 Correct 355 ms 18260 KB Output is correct
10 Correct 1107 ms 42304 KB Output is correct
11 Correct 712 ms 42688 KB Output is correct
12 Correct 713 ms 41152 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 493 ms 37952 KB Output is correct
15 Correct 81 ms 3052 KB Output is correct
16 Correct 1194 ms 42264 KB Output is correct
17 Correct 1029 ms 41792 KB Output is correct
18 Correct 1037 ms 41672 KB Output is correct
19 Execution timed out 3073 ms 45304 KB Time limit exceeded
20 Halted 0 ms 0 KB -