Submission #49730

#	Time	Username	Problem	Language	Result	Execution time	Memory
49730		imeimi2000	Worst Reporter 2 (JOI16_worst_reporter2)	C++17	100 / 100	841 ms	41172 KiB

worst_reporter2

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n;
const int MAXN = 2e5 + 1;
const int inf = 1e8;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
pii ev[MAXN << 1];
pii seg[1 << 19];
int lazy[1 << 19];
set<int> as, cs;
set<int> mp[MAXN];

void init(int i, int s, int e) {
    seg[i].second = s;
    if (s == e) return;
    int m = (s + e) / 2;
    init(i << 1, s, m);
    init(i << 1 | 1, m + 1, e);
}

void update(int i, int s, int e, int x, int y, int v) {
    if (e < x || y < s) return;
    if (x <= s && e <= y) {
        lazy[i] += v;
        seg[i].first += v;
        return;
    }
    int m = (s + e) / 2;
    update(i << 1, s, m, x, y, v);
    update(i << 1 | 1, m + 1, e, x, y, v);
    seg[i] = min(seg[i << 1], seg[i << 1 | 1]);
    seg[i].first += lazy[i];
}

pii query(int i, int s, int e, int x, int y) {
    if (e < x || y < s) return pii(inf, -1);
    if (x <= s && e <= y) return seg[i];
    int m = (s + e) / 2;
    pii ret = min(query(i << 1, s, m, x, y), query(i << 1 | 1, m + 1, e, x, y));
    ret.first += lazy[i];
    return ret;
}

void newMatching(int ax, int cx) {
    int x = lower_bound(d, d + n, b[ax]) - d;
    update(1, 0, n - 1, x, cx - 1, -1);
}

int main() {
    scanf("%d", &n);
    for (int i = n; i--; ) {
        scanf("%d%d", a + i, b + i);
        ev[i] = { b[i], i };
    }
    
    for (int i = n; i--; ) {
        scanf("%d%d", c + i, d + i);
        ev[i + n] = { d[i], i + n };
    }
    
    sort(ev, ev + (n << 1));
    
    init(1, 0, n - 1);
    int cnt = 0, ans = 0;
    for (int i = 0; i < (n << 1); ++i) {
        int sc, x;
        tie(sc, x) = ev[i];
        if (x < n) {
            ++cnt;
            mp[a[x]].insert(x);
            as.insert(x);
        }
        else {
            x -= n;
            update(1, 0, n - 1, x, x, --cnt);
            if (mp[c[x]].empty()) {
                cs.insert(x);
            }
            else {
                ++ans;
                int ax = *mp[c[x]].rbegin();
                mp[c[x]].erase(ax);
                as.erase(ax);
                newMatching(ax, x);
            }
            while (1) {
                pii ret = query(1, 0, n - 1, 0, x);
                if (ret.first) break;
                int t = ret.second, cx;
                while (!cs.empty() && (cx = *cs.begin()) <= t) {
                    int ax = *as.begin();
                    as.erase(ax);
                    cs.erase(cx);
                    mp[a[ax]].erase(ax);
                    newMatching(ax, cx);
                }
                update(1, 0, n - 1, t, t, inf);
            }
        }
    }
    
    printf("%d\n", n - ans);
	return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
worst_reporter2.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", a + i, b + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", c + i, d + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40