제출 #288682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288682		emil_physmath	벽 (IOI14_wall)	C++17	8 / 100	270 ms	48320 KiB

wall

#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 maxN = 100'005;
const int maxH = 100'000;

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

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

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

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