oj.uz

Submission #288392

# Submission time Handle Problem Language Result Execution time Memory
288392 2020-09-01T13:11:11 Z emil_physmath Wall (IOI14_wall) C++17
32 / 100
 509 ms 22652 KB 
#include "wall.h"
#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 maxN = 100'005;

int t1[4 * maxN], t2[4 * maxN];

void Maxi(int* t, int v, int vl, int vr, int l, int r, int x) {
    if (l > vr || vl > r) return;
    if (l <= vl && vr <= r) {
        t[v] = max(t[v], x);
        return;
    }
    int vm = (vl + vr) / 2;
    Maxi(t, v * 2, vl, vm, l, r, x);
    Maxi(t, v * 2 + 1, vm + 1, vr, l, r, x);
}
void Mini(int* t, int v, int vl, int vr, int l, int r, int x) {
    if (l > vr || vl > r) return;
    if (l <= vl && vr <= r) {
        t[v] = min(t[v], x);
        return;
    }
    int vm = (vl + vr) / 2;
    Mini(t, v * 2, vl, vm, l, r, x);
    Mini(t, v * 2 + 1, vm + 1, vr, l, r, x);
}
int GetMin(int* t, int v, int vl, int vr, int i)
{
    if (vl == vr)
        return t[v];
    int vm = (vl + vr) / 2;
    if (i <= vm) return min(t[v], GetMin(t, v * 2, vl, vm, i));
    return min(t[v], GetMin(t, v * 2 + 1, vm + 1, vr, i));
}
int GetMax(int* t, int v, int vl, int vr, int i)
{
    if (vl == vr)
        return t[v];
    int vm = (vl + vr) / 2;
    if (i <= vm) return max(t[v], GetMax(t, v * 2, vl, vm, i));
    return max(t[v], GetMax(t, v * 2 + 1, vm + 1, vr, i));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int ans[])
{
    for (int i = 0; i < 4 * n; ++i)
        t1[i] = 0, t2[i] = 1000'000'000;
    for (int i = 0; i < n; ++i)
        ans[i] = 0;
    if (n <= 10000 && k <= 5000) {
        for (int x = 0; x < k; ++x)
            if (op[x] == 1) // Add
            {
                for (int i = left[x]; i <= right[x]; ++i)
                    ans[i] = max(ans[i], height[x]);
            }
            else // Remove
            {
                for (int i = left[x]; i <= right[x]; ++i)
                    ans[i] = min(ans[i], height[x]);
            }
        return;
    }
    for (int x = 0; x < k; ++x)
        if (op[x] == 1) // Add
            Maxi(t1, 1, 0, n - 1, left[x], right[x], height[x]);
        else // Remove
            Mini(t2, 1, 0, n - 1, left[x], right[x], height[x]);
    for (int i = 0; i < n; ++i)
    {
        ans[i] = GetMax(t1, 1, 0, n - 1, i);
        ans[i] = min(ans[i], GetMin(t2, 1, 0, n - 1, i));
    }
}

Compilation message

wall.cpp:10: warning: "BUGO" redefined
   10 | #define BUGO(x)
      | 
wall.cpp:7: note: this is the location of the previous definition
    7 | #define BUGO(x) cerr << #x << " = " << (x) << '\n';
      | 
wall.cpp:11: warning: "BUGOARR" redefined
   11 | #define BUGOARR(x)
      | 
wall.cpp:8: note: this is the location of the previous definition
    8 | #define BUGOARR(a) {cerr << #a << ": "; for (auto i: a) cerr << i << ' '; cerr << '\n';}
      | 
wall.cpp:13:46: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   13 | ostream& operator<<(ostream& out, const pair<auto, auto>& p) {
      |                                              ^~~~
wall.cpp:13:52: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   13 | 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:15:1: warning: no return statement in function returning non-void [-Wreturn-type]
   15 | }
      | ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 20 ms 768 KB Output is correct
5 Correct 20 ms 768 KB Output is correct
6 Correct 20 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 180 ms 8228 KB Output is correct
3 Correct 178 ms 8056 KB Output is correct
4 Correct 509 ms 21624 KB Output is correct
5 Correct 349 ms 22652 KB Output is correct
6 Correct 329 ms 20976 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 20 ms 768 KB Output is correct
5 Correct 20 ms 768 KB Output is correct
6 Correct 20 ms 768 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 175 ms 8116 KB Output is correct
9 Correct 177 ms 8056 KB Output is correct
10 Correct 501 ms 21496 KB Output is correct
11 Correct 350 ms 22520 KB Output is correct
12 Correct 322 ms 20984 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Incorrect 182 ms 13944 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 22 ms 768 KB Output is correct
5 Correct 20 ms 768 KB Output is correct
6 Correct 20 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 182 ms 8232 KB Output is correct
9 Correct 174 ms 8064 KB Output is correct
10 Correct 488 ms 21496 KB Output is correct
11 Correct 345 ms 22520 KB Output is correct
12 Correct 326 ms 20984 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Incorrect 182 ms 13976 KB Output isn't correct
15 Halted 0 ms 0 KB -