oj.uz

Submission #288705

# Submission time Handle Problem Language Result Execution time Memory
288705 2020-09-01T19:23:52 Z emil_physmath Wall (IOI14_wall) C++17
61 / 100
 3000 ms 42688 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;
    });
    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:83: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]
   83 |         while (ind < upd.size() && upd[ind].time <= i)
      |                ~~~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 28 ms 896 KB Output is correct
5 Correct 29 ms 896 KB Output is correct
6 Correct 29 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 326 ms 39616 KB Output is correct
3 Correct 295 ms 16852 KB Output is correct
4 Correct 974 ms 40128 KB Output is correct
5 Correct 558 ms 40000 KB Output is correct
6 Correct 546 ms 40000 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 896 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 26 ms 896 KB Output is correct
5 Correct 29 ms 896 KB Output is correct
6 Correct 29 ms 896 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 328 ms 39616 KB Output is correct
9 Correct 319 ms 16724 KB Output is correct
10 Correct 985 ms 40048 KB Output is correct
11 Correct 568 ms 40324 KB Output is correct
12 Correct 562 ms 40108 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 338 ms 39616 KB Output is correct
15 Correct 86 ms 2924 KB Output is correct
16 Correct 1041 ms 40128 KB Output is correct
17 Correct 869 ms 40132 KB Output is correct
18 Correct 877 ms 40228 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 3 ms 896 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 29 ms 896 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 332 ms 39616 KB Output is correct
9 Correct 301 ms 16852 KB Output is correct
10 Correct 1008 ms 40000 KB Output is correct
11 Correct 560 ms 40128 KB Output is correct
12 Correct 550 ms 40012 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 336 ms 39616 KB Output is correct
15 Correct 73 ms 2924 KB Output is correct
16 Correct 1032 ms 40052 KB Output is correct
17 Correct 884 ms 40128 KB Output is correct
18 Correct 889 ms 40144 KB Output is correct
19 Execution timed out 3094 ms 42688 KB Time limit exceeded
20 Halted 0 ms 0 KB -