Submission #602413

#	Time	Username	Problem	Language	Result	Execution time	Memory
602413		AA_Surely	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	302 ms	34692 KiB

event2

#include <bits/stdc++.h>

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

const int N = 2e5 + 7;
const int LOG = 20;
const int INF = 1e9 + 7;

#define lc now << 1
#define rc now << 1 | 1

int n, k;
int ns[N][2], up[N][LOG];
int mnr[N];
VI comp;
set<int> ll, rr;

struct SegTree {
    int tree[N << 2], lz[N << 2];

    void shift(int now, int l, int r) {
        int mid = (l + r) >> 1;

        tree[lc] += lz[now] * (mid - l + 1);
        lz[lc] += lz[now];

        tree[rc] += lz[now] * (r - mid);
        lz[rc] += lz[now];

        lz[now] = 0;
        return;
    }

    void make1(int lq, int rq, int now = 1, int ls = 0, int rs = N - 1) {
        if (rq < lq || rq < ls || rs < lq) return;
        if (lq <= ls && rs <= rq) {
            tree[now] += (rs - ls + 1);
            lz[now] = 1;
            return;
        }

        int mid = (ls + rs) >> 1;
        shift(now, ls, rs);
        make1(lq, rq, lc, ls, mid);
        make1(lq, rq, rc, mid + 1, rs);

        tree[now] = tree[lc] + tree[rc];
    }

    int get(int lq, int rq, int now = 1, int ls = 0, int rs = N - 1) {
        if (rq < lq || rq < ls || rs < lq) return 0;
        if (lq <= ls && rs <= rq) return tree[now];
        
        int mid = (ls + rs) >> 1;
        shift(now, ls, rs);
        return get(lq, rq, lc, ls, mid) + get(lq, rq, rc, mid + 1, rs);
    }
} tree;

void init() {
    cin >> n >> k;

    F0R(i, n) {
        cin >> ns[i][0] >> ns[i][1];
        ns[i][1]--;
        comp.PB(ns[i][0]);
        comp.PB(ns[i][1]);
    }

    sort(ALL(comp));
    comp.resize(unique(ALL(comp)) - comp.begin());
    F0R(i, n) F0R(j, 2) ns[i][j] = lower_bound(ALL(comp), ns[i][j]) - comp.begin() + 1;

    return;
}

void precalc() {
    fill(mnr, mnr + N, INF);

    F0R(i, n) mnr[ ns[i][0] ] = min(mnr[ ns[i][0] ], ns[i][1]);
    up[N - 1][0] = mnr[N - 1];
    R0F(i, N - 1) up[i][0] = min(up[i + 1][0], mnr[i]);

    FOR(k, 1, LOG) F0R(i, N) {
        up[i][k] = INF;
        if (up[i][k - 1] < N - 1)
            up[i][k] = up[ up[i][k - 1] + 1 ][k - 1];
    }

    return;
}

int maxIn(int l, int r) {
    int cnt = 0;
    R0F(i, LOG) if (l < N && up[l][i] <= r) {
        cnt += (1 << i);
        l = up[l][i] + 1;
    }

    return cnt;
}

int main() {
    IOS;

    init();
    precalc();
    
    int mx = maxIn(0, N - 1);
    if (mx < k) return cout << -1, 0;
    
    rr.insert(0);
    ll.insert(N - 1);
    
    VI ans;
    F0R(i, n) {
        if (ans.size() == k || tree.get(ns[i][0], ns[i][1])) continue;
        int lft = *(--rr.lower_bound(ns[i][0]));
        int rgt = *ll.lower_bound(ns[i][1]);
        int tmp = mx - maxIn(lft + 1, rgt - 1) + maxIn(lft + 1, ns[i][0] - 1) + maxIn(ns[i][1] + 1, rgt - 1) + 1;

        if (tmp >= k) {
            mx = tmp;
            tree.make1(ns[i][0], ns[i][1]);
            ll.insert(ns[i][0]);
            rr.insert(ns[i][1]);
            ans.PB(i + 1);
        }
    }

    for(int on : ans) cout << on << '\n';
    return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:142:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  142 |         if (ans.size() == k || tree.get(ns[i][0], ns[i][1])) continue;
      |             ~~~~~~~~~~~^~~~

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61