제출 #1281322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281322		ducanh0811	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	313 ms	28356 KiB

matryoshka

#include <bits/stdc++.h>
bool M1;
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;

#define MAXN 200005
int numGift, numQuery;
pair<int, int> gift[MAXN];
struct query {
    int a, b, i;
};
query vecQuery[MAXN];
vector<int> compR, compH;
int res[MAXN];

struct BIT {
    int n;
    vector<int> bit;
    BIT(int _n = 0) {
        n = _n;
        bit.assign(n + 5, 0);
    }

    void update(int p, int val) {
        for (; p <= n; p += p & -p) bit[p] += val;
    }

    int get(int x) {
        int res = 0;
        while (x) res += bit[x], x -= x & -x;
        return res;
    }
} tree;

multiset<int> ms;

///++++++++++++++++++++++++++++++++++++++///

void compression() {
    FOR(i, 1, numGift) {
        compR.push_back(gift[i].first);
        compH.push_back(gift[i].second);
    }
    FOR(i, 1, numQuery) {
        compR.push_back(vecQuery[i].a);
        compH.push_back(vecQuery[i].b);
    }
    sort(compR.begin(), compR.end());
    sort(compH.begin(), compH.end());
    compR.erase(unique(compR.begin(), compR.end()), compR.end());
    compH.erase(unique(compH.begin(), compH.end()), compH.end());
    FOR(i, 1, numGift) {
        gift[i].first = lower_bound(compR.begin(), compR.end(), gift[i].first) - compR.begin() + 1;
        gift[i].second = lower_bound(compH.begin(), compH.end(), gift[i].second) - compH.begin() + 1;
    }
    FOR(i, 1, numQuery) {
        vecQuery[i].a = lower_bound(compR.begin(), compR.end(), vecQuery[i].a) - compR.begin() + 1;
        vecQuery[i].b = lower_bound(compH.begin(), compH.end(), vecQuery[i].b) - compH.begin() + 1;
    }
}

void solve() {
    cin >> numGift >> numQuery;
    FOR(i, 1, numGift) {
        int r, h; cin >> r >> h;
        gift[i] = make_pair(r, h);
    }
    FOR(i, 1, numQuery) {
        int a, b; cin >> a >> b;
        vecQuery[i] = {a, b, i};
    }
    compression();
    sort(gift + 1, gift + 1 + numGift, [](const pair<int, int> &a, const pair<int, int> &b){
        return a.first > b.first;
    });
    sort(vecQuery + 1, vecQuery + 1 + numQuery, [](const query &a, const query &b) {
        return a.a > b.a;
    });
    tree = BIT(compH.size());
    int ptrGift = 1;
    FOR(i, 1, numQuery) {
        query &t = vecQuery[i];
        while (ptrGift <= numGift && gift[ptrGift].first >= t.a) {
            int nextGift = ptrGift;
            while (nextGift <= numGift && gift[nextGift].first == gift[ptrGift].first) nextGift++;
            vector<int> vecUpdate;
            FOR(j, ptrGift, nextGift - 1) {
                auto it = ms.upper_bound(gift[j].second);
                if (it == ms.end()){
                    vecUpdate.push_back(gift[j].second);
                } else {
                    tree.update(*it, -1);
                    ms.erase(it);
                    vecUpdate.push_back(gift[j].second);
                }
            }
            for (int &num : vecUpdate){
                ms.insert(num);
                tree.update(num, 1);
            }
            ptrGift = nextGift;
        }
        res[t.i] = tree.get(t.b);
    }
    FOR(i, 1, numQuery) {
        cout << res[i] << '\n';
    }
}

///++++++++++++++++++++++++++++++++++++++///

#define task "HOPQUA"
int32_t main() {
    if (fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    solve();
//    bool M2;
//    cerr << "++++++++++++++++++++++++++++\n";
//    cerr << "Time: " << clock() << "ms" << '\n';
//    cerr << "Memory: " << abs(&M2 - &M1) / 1024 / 1024 << "MB" << '\n';
//    cerr << "++++++++++++++++++++++++++++\n";
    return 0;
}

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

matryoshka.cpp: In function 'int32_t main()':
matryoshka.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49