제출 #288392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288392		emil_physmath	Wall (IOI14_wall)	C++17	32 / 100	509 ms	22652 KiB

wall

#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));
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39