Submission #1157627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157627		mocha	단층 (JOI16_ho_t5)	C++20	100 / 100	157 ms	10912 KiB

2016_ho_t5

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
const int mx = 2e5+5;

int n, q;
pair<int, int> p[mx];

struct node {
    int x, ty, l;
} qu[mx];

int bit[2][mx];

void insert(int idx, int id, int x) {
    for (int i=id;i<mx;i+=i&-i) {
        bit[idx][i] += x;
    }
}

int query(int idx, int id) {
    int ans = 0;
    for (int i=id;i>0;i-=i&-i) ans += bit[idx][i];
    return ans;
}

signed main() {
    cin >> n >> q;
    for (int i=1;i<=n;i++) insert(0, i, 1);
//    for (int i=1;i<=n;i++) p[i] = {i, 0};
    for (int i=1;i<=q;i++) {
        cin >> qu[i].x >> qu[i].ty >> qu[i].l;
    }
//    for (int i=1;i<=n;i++) cout << query(0, i) << " ";
//    cout << "\n";
    for (int i=q;i>=1;i--) {
        auto [x, ty, L] = qu[i];
        if (ty == 1) {
            int l = 0, r = n;
            while (l < r) {
                int m = l + r + 1 >> 1;
                if (query(0, m) <= x) l = m;
                else r = m-1;
            }
            if (l == 0) continue;
            insert(1, 1, L);
            insert(1, l+1, -L);
//            for (int i=1;i<=n;i++) {
//                if (p[i].ff <= x) p[i].ss += L;
//            }
        } else {
            int l = 1, r = n+1;
            while (l < r) {
                int m = l + r >> 1;
                if (query(0, m) - 2 * query(1, m) > x) r = m;
                else l = m + 1;
            }
            insert(0, l, 2*L);
            insert(1, l, L);
//            for (int i=1;i<=n;i++) {
//                int X = p[i].ff - 2 * p[i].ss, Y = 0;
//                if (X > x) {
//                    p[i].ff += 2 * L;
//                    p[i].ss += L;
//                }
//            }
        }
    }
//    for (int i=1;i<=n;i++) cout << p[i].ss << "\n";
    for (int i=1;i<=n;i++) cout << query(1, i) << "\n";
//    for (int i=1;i<=n;i++) cout << p[i].ff - 2*p[i].ss << " ";
}

• Subtask 1: 18 / 18
• Subtask 2: 16 / 16
• Subtask 3: 66 / 66