Submission #844468

#	Time	Username	Problem	Language	Result	Execution time	Memory
844468		mickey080929	Worst Reporter 2 (JOI16_worst_reporter2)	C++17	100 / 100	201 ms	32704 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;
typedef pair<int,int> pii;

pii A[201010], B[201010];
vector<int> v[201010];

struct LazySegmentTree{
    int tree[401010 * 4];
    int lazy[401010 * 4];
    void init(int n) {
        fill(tree, tree+n*4+10, inf);
        fill(lazy, lazy+n*4+10, 0);
    }
    void propagate(int node, int s, int e) {
        if (!lazy[node]) return;
        tree[node] += lazy[node];
        if (s != e) {
            lazy[node<<1] += lazy[node];
            lazy[node<<1|1] += lazy[node];
        }
        lazy[node] = 0;
    }
    void update_point(int node, int s, int e, int tar, int val) {
        propagate(node, s, e);
        if (s > tar || tar > e) return;
        if (s == e) {
            tree[node] = val;
            return;
        }
        int mid = s + e >> 1;
        update_point(node<<1, s, mid, tar, val);
        update_point(node<<1|1, mid+1, e, tar, val);
        tree[node] = min(tree[node<<1], tree[node<<1|1]);
    }
    void update_range(int node, int s, int e, int l, int r, int val) {
        propagate(node, s, e);
        if (l > e || s > r) return;
        if (l <= s && e <= r) {
            lazy[node] = val;
            propagate(node, s, e);
            return;
        }
        int mid = s + e >> 1;
        update_range(node<<1, s, mid, l, r, val);
        update_range(node<<1|1, mid+1, e, l, r, val);
        tree[node] = min(tree[node<<1], tree[node<<1|1]);
    }
    int query(int node, int s, int e, int l, int r) {
        propagate(node, s, e);
        if (l > e || s > r) return inf;
        if (l <= s && e <= r) return tree[node];
        int mid = s + e >> 1;
        return min(query(node<<1, s, mid, l, r), query(node<<1|1, mid+1, e, l, r));
    }
} seg;

int main() {
    int n;
    scanf("%d", &n);
    vector<int> t;
    for (int i=1; i<=n; i++) {
        scanf("%d %d", &A[i].first, &A[i].second);
        t.push_back(A[i].second);
    }
    for (int i=1; i<=n; i++) {
        scanf("%d %d", &B[i].first, &B[i].second);
        t.push_back(B[i].second);
    }
    reverse(A+1, A+n+1);
    reverse(B+1, B+n+1);
    sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());
    int m = (int) t.size();
    for (int i=1; i<=n; i++) {
        A[i].second = lower_bound(t.begin(), t.end(), A[i].second) - t.begin() + 1;
        B[i].second = lower_bound(t.begin(), t.end(), B[i].second) - t.begin() + 1;
    }
    seg.init(m);
    int j = 1, ans = 0;
    for (int i=1; i<=n; i++) {
        while (j <= n && A[j].second <= B[i].second) {
            v[A[j].first].push_back(A[j].second);
            j ++;
        }
        if (v[B[i].first].empty() || seg.query(1, 1, m, v[B[i].first].back(), m) <= 0) {
            seg.update_point(1, 1, m, B[i].second, j - i - 1);
            ans ++;
        }
        else {
            seg.update_range(1, 1, m, v[B[i].first].back(), m, -1);
            v[B[i].first].pop_back();
        }
    }
    printf("%d\n", ans);
}

Compilation message (stderr)

worst_reporter2.cpp: In member function 'void LazySegmentTree::update_point(int, int, int, int, int)':
worst_reporter2.cpp:34:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int mid = s + e >> 1;
      |                   ~~^~~
worst_reporter2.cpp: In member function 'void LazySegmentTree::update_range(int, int, int, int, int, int)':
worst_reporter2.cpp:47:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mid = s + e >> 1;
      |                   ~~^~~
worst_reporter2.cpp: In member function 'int LazySegmentTree::query(int, int, int, int, int)':
worst_reporter2.cpp:56:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid = s + e >> 1;
      |                   ~~^~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
worst_reporter2.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%d %d", &A[i].first, &A[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%d %d", &B[i].first, &B[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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