Submission #1223282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223282		khoile08	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	264 ms	19196 KiB

matryoshka

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
//#define int long long
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define db double
#define lcm(a,b) a / __gcd(a, b) * b
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define iv pair<pair<int,int>,pair<int,int>>
#define sq(a) (a) * (a)
#define MASK(i) (1LL << i)
#define task "task"

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;

int n, q;
int ans[N];
vector<int> val;
ii a[2 * N];

struct Query {
    int a, b, id;
};
Query qu[N];

struct Bit {
    int bit[2 * N];

    void up(int x, int val) {
        for(; x <= 2 * n; x += x & -x) bit[x] = max(bit[x], val);
    }

    int get(int x) {
        int ret = 0;
        for(; x; x -= x & -x) ret = max(ret, bit[x]);
        return ret;
    }
};
Bit bit;

struct Smt {
    int seg[8 * N], lz[8 * N];

    void push(int id) {
        int val = lz[id];
        if(val != 0) {
            seg[id << 1] = max(seg[id << 1], val);
            seg[id << 1 | 1] = max(seg[id << 1 | 1], val);
            lz[id << 1] = max(lz[id << 1], val);
            lz[id << 1 | 1] = max(lz[id << 1 | 1], val);
            lz[id] = 0;
        }
    }

    void up(int id, int l, int r, int u, int v, int val) {
        if(l > v || r < u) return;
        if(l >= u && r <= v) {
            seg[id] = max(seg[id], val);
            lz[id] = max(lz[id], val);
            return;
        }
        int mid = l + r >> 1;
        push(id);
        up(id << 1, l, mid, u, v, val);
        up(id << 1 | 1, mid + 1, r, u, v, val);
        seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
    }

    int get(int id, int l, int r, int pos) {
        if(pos < l || pos > r) return 0;
        if(l == r) return seg[id];
        int mid = l + r >> 1;
        push(id);
        return max(get(id << 1, l, mid, pos), get(id << 1 | 1, mid + 1, r, pos));
    }
};
Smt it;

void Solve() {
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    FOR(i, 1, n) a[i].se = lower_bound(val.begin(), val.end(), a[i].se) - val.begin() + 1;
    FOR(i, 1, n) qu[i].b = lower_bound(val.begin(), val.end(), qu[i].b) - val.begin() + 1;

    sort(a + 1, a + 1 + n + q, [&] (ii &a, ii &b) {
        return (a.fi == b.fi ? a.se < b.se : a.fi > b.fi);
    });
    sort(qu + 1, qu + 1 + q, [&] (Query &a, Query &b) {
        return a.a > b.a;
    });

//    FOR(i, 1, n + q) {
//        cout << a[i].fi << ' ' << a[i].se << '\n';
//    }
//    cout << '\n';

    int p = 1;
    FOR(i, 1, n + q) {
        if(a[i].se != (int)2e9) {
//            cout << a[i].se << ' ';
            int mx = bit.get(a[i].se) + 1;
            bit.up(a[i].se, mx);
            it.up(1, 1, 2 * n, a[i].se, 2 * n, mx);
//            cout << mx << '\n';
        }
        if(a[i].se == (int)2e9) {
            while(p <= q && qu[p].a == a[i].fi) {
//                cout << qu[p].a << ' ' << qu[p].b << ' ' << qu[p].id << ' ' << a[i].fi << '\n';
                ans[qu[p].id] = it.get(1, 1, 2 * n, qu[p].b);
                p++;
            }
        }
    }
    FOR(i, 1, q) {
        cout << ans[i] << '\n';
    }
}

signed main() {
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int test = 1;
//    cin >> test;
    while(test--) {
        cin >> n >> q;
        FOR(i, 1, n) {
            cin >> a[i].fi >> a[i].se;
            val.pb(a[i].se);
        }
        FOR(i, 1, q) {
            cin >> qu[i].a >> qu[i].b;
            qu[i].id = i;
            val.pb(qu[i].b);
            a[i + n] = {qu[i].a, (int)2e9};
        }
        Solve();
    }
}

Compilation message (stderr)

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

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