Submission #60347038

Source Code Expand

#include <bits/stdc++.h>
using i64 = long long;
// #define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using std::cerr;
using std::max, std::min, std::swap, std::array;
using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

const int N = 2e5 + 5;

struct SGT {
    #define ls (p << 1)
    #define rs (p << 1 | 1)
    #define mid (l + r >> 1)
    int mx[N << 2], tag[N << 2];

    void pushup(int p) {
        mx[p] = max(mx[ls], mx[rs]);
    }
    void pushdown(int p) {
        if (tag[p] == 0) return;
        mx[ls] = max(mx[ls], tag[p]);
        mx[rs] = max(mx[rs], tag[p]);
        tag[ls] = max(tag[ls], tag[p]);
        tag[rs] = max(tag[rs], tag[p]);
        tag[p] = 0;
    }

    int qry(int p, int l, int r, int ql, int qr) {
        if (ql <= l and r <= qr) {
            return mx[p];
        }
        int res = 0;
        pushdown(p);
        if (ql <= mid) res = max(res, qry(ls, l, mid, ql, qr));
        if (mid < qr) res = max(res, qry(rs, mid + 1, r, ql, qr));
        pushup(p);
        return res;
    }
    void upd(int p, int l, int r, int ql, int qr, int x) {
        if (ql <= l and r <= qr) {
            mx[p] = max(mx[p], x);
            tag[p] = max(tag[p], x);
            return;
        }
        pushdown(p);
        if (ql <= mid) upd(ls, l, mid, ql, qr, x);
        if (mid < qr) upd(rs, mid + 1, r, ql, qr, x);
        pushup(p);
    }
} sgt;

void solve() {
    int h = read();
    int w = read();
    int n = read();

    using tup = std::tuple<int, int, int>;
    vector<vector<tup>> a(h + 1);

    for (int i = 1; i <= n; i++) {
        int r = h - read() + 1;
        int c = read();
        int l = read();

        // cerr << r << " " << c << " " << c + l - 1 << '\n';
        a[r].eb(c, c + l - 1, i);
    }

    vector<int> ans(n + 1);
    for (int i = 1; i <= h; i++) {
        for (auto [l, r, idx] : a[i]) {
            // cout << i << " " << sgt.qry(1, 1, w, l, r);
            ans[idx] = sgt.qry(1, 1, w, l, r) + 1;
            sgt.upd(1, 1, w, l, r, ans[idx]);

            // cout << " " << ans[idx] << '\n';
        }
    }

    for (int i = 1; i <= n; i++) {
        // cout << ans[i] << "\n";
        cout << h - ans[i] + 1 << "\n";
    }
}

signed main() {
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}

Submission Info

Submission Time
Task F - Falling Bars
User TosakaUCW
Language C++ 20 (gcc 12.2)
Score 525
Code Size 2621 Byte
Status AC
Exec Time 224 ms
Memory 18620 KiB

Compile Error

Main.cpp: In member function ‘int SGT::qry(int, int, int, int, int)’:
Main.cpp:21:20: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   21 |     #define mid (l + r >> 1)
      |                  ~~^~~
Main.cpp:42:19: note: in expansion of macro ‘mid’
   42 |         if (ql <= mid) res = max(res, qry(ls, l, mid, ql, qr));
      |                   ^~~
Main.cpp:21:20: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   21 |     #define mid (l + r >> 1)
      |                  ~~^~~
Main.cpp:42:50: note: in expansion of macro ‘mid’
   42 |         if (ql <= mid) res = max(res, qry(ls, l, mid, ql, qr));
      |                                                  ^~~
Main.cpp:21:20: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   21 |     #define mid (l + r >> 1)
      |                  ~~^~~
Main.cpp:43:13: note: in expansion of macro ‘mid’
   43 |         if (mid < qr) res = max(res, qry(rs, mid + 1, r, ql, qr));
      |             ^~~
Main.cpp:21:20: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   21 |     #define mid (l + r >> 1)
      |                  ~~^~~
Main.cpp:43:46: note: in expansion of macro ‘mid’
   43 |         if (mid < qr) res = max(res, qry(rs, mid + 1, r, ql, qr));
      |                                              ^~~
Main.cpp: In member function ‘void SGT::upd(int, int, int, int, int, int)’:
Main.cpp:21:20: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   21 |     #define mid (l + r >> 1)
      |                  ~~^~~
Main.cpp:54:19: note: in expansion of macro ‘mid’
   54 |         if (ql <= mid) upd(ls, l, mid, ql, qr, x);
      |                   ^~~
Main.cpp:21:20: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   21 |     #define mid (l + r >> 1)
      |                  ~~^~~
Main.cpp:54:35: note: in expansion of macro ‘mid’
   54 |         if (ql <= mid) upd(ls, l, mid, ql, qr, x);
      |                                   ^~~
Main.cpp:21:20: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   21 |     #define mid (l + r >> 1)
      |                  ~~^~~
Main.cpp:55:13: note: in expansion of macro ‘mid’
   55 |         if (mid < qr) upd(rs, mid + 1, r, ql, qr, x);
      |             ^~~
Main.cpp:21:20: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   21 |     #define mid (l + r >> 1)
      |                  ~~^~~
Main.cpp:55:31: note: in expansion of macro ‘mid’
   55 |         if (mid < qr) upd(rs, mid + 1, r, ql, qr, x);
      |                               ^~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 525 / 525
Status
AC × 3
AC × 52
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 02_handmade_00.txt, 02_handmade_01.txt, 02_handmade_02.txt, 02_handmade_03.txt, 02_handmade_04.txt, 02_handmade_05.txt, 02_handmade_06.txt, 02_handmade_07.txt, 02_handmade_08.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3520 KiB
00_sample_01.txt AC 1 ms 3584 KiB
00_sample_02.txt AC 1 ms 3524 KiB
01_random_00.txt AC 53 ms 8132 KiB
01_random_01.txt AC 56 ms 9716 KiB
01_random_02.txt AC 100 ms 9240 KiB
01_random_03.txt AC 90 ms 8548 KiB
01_random_04.txt AC 54 ms 7672 KiB
01_random_05.txt AC 124 ms 9584 KiB
01_random_06.txt AC 97 ms 8244 KiB
01_random_07.txt AC 75 ms 7836 KiB
01_random_08.txt AC 99 ms 9128 KiB
01_random_09.txt AC 90 ms 8144 KiB
01_random_10.txt AC 70 ms 11000 KiB
01_random_11.txt AC 47 ms 8360 KiB
01_random_12.txt AC 48 ms 7892 KiB
01_random_13.txt AC 103 ms 8560 KiB
01_random_14.txt AC 146 ms 10164 KiB
01_random_15.txt AC 59 ms 6932 KiB
01_random_16.txt AC 90 ms 8184 KiB
01_random_17.txt AC 65 ms 8592 KiB
01_random_18.txt AC 95 ms 10800 KiB
01_random_19.txt AC 114 ms 9736 KiB
01_random_20.txt AC 153 ms 16848 KiB
01_random_21.txt AC 142 ms 16796 KiB
01_random_22.txt AC 224 ms 17432 KiB
01_random_23.txt AC 205 ms 17432 KiB
01_random_24.txt AC 223 ms 17364 KiB
01_random_25.txt AC 222 ms 17496 KiB
01_random_26.txt AC 212 ms 17448 KiB
01_random_27.txt AC 205 ms 17340 KiB
01_random_28.txt AC 101 ms 17512 KiB
01_random_29.txt AC 97 ms 17496 KiB
01_random_30.txt AC 148 ms 16472 KiB
01_random_31.txt AC 136 ms 16536 KiB
01_random_32.txt AC 223 ms 17004 KiB
01_random_33.txt AC 217 ms 17164 KiB
01_random_34.txt AC 222 ms 17072 KiB
01_random_35.txt AC 209 ms 17088 KiB
01_random_36.txt AC 220 ms 17116 KiB
01_random_37.txt AC 223 ms 17096 KiB
01_random_38.txt AC 140 ms 17084 KiB
01_random_39.txt AC 133 ms 16984 KiB
02_handmade_00.txt AC 33 ms 14728 KiB
02_handmade_01.txt AC 33 ms 14668 KiB
02_handmade_02.txt AC 54 ms 14688 KiB
02_handmade_03.txt AC 47 ms 14764 KiB
02_handmade_04.txt AC 98 ms 9828 KiB
02_handmade_05.txt AC 169 ms 16844 KiB
02_handmade_06.txt AC 127 ms 18480 KiB
02_handmade_07.txt AC 125 ms 18620 KiB
02_handmade_08.txt AC 1 ms 3536 KiB