Submission #1281275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281275		enxiayy	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	113 ms	7288 KiB

matryoshka

#include <bits/stdc++.h>

using namespace std;

#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
#define ff first
#define ss second
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), v.end())
#define dbg(v) "[" #v " = " << (v) << "]"
#define el "\n"

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;

template<class T> bool minimize(T& a, const T& b){ if(a > b) return a = b, true; return false; } 
template<class T> bool maximize(T& a, const T& b){ if(a < b) return a = b, true; return false; } 

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long randRange(long long l, long long r){ return uniform_int_distribution<long long>(l,r)(rng); }

const int N = 2e5 + 5;

struct gift {
    int x, y;
    gift(int x = 0, int y = 0) : x(x), y(y) {}

    bool operator < (const gift& other) const {
        if (x == other.x) return y < other.y;
        else return x > other.x;
    }
} a[N];

struct query {
    int l, r, id;
    query(int l = 0, int r = 0, int id = 0) : l(l), r(r), id(id) {}

    bool operator < (const query& other) const {
        return l > other.l;
    }
} eq[N];

int n, q;
vector<int> lis;

void update(int x) {
    int k = upper_bound(all(lis), x) - lis.begin();
    if (k == sz(lis)) lis.eb(x);
    else lis[k] = x;
}

int get(int x) {
    int l = 0;
    int r = sz(lis) - 1;
    int ans = -1;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if (lis[mid] <= x) {
            ans = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }

    return ans + 1;
}

int ans[N];

void solve() {
    cin >> n >> q;
    FOR(i, 1, n) cin >> a[i].x >> a[i].y;
    sort(a + 1, a + 1 + n);
    FOR(i, 1, q) {
        cin >> eq[i].l >> eq[i].r;
        eq[i].id = i;
    }
    sort(eq + 1, eq + 1 + q);

    int p = 1;
    FOR(i, 1, q) {
        // cerr << eq[i].l << ": ";
        while(a[p].x >= eq[i].l) {
            update(a[p].y);
            // cerr << a[p].y << " ";
            ++p;
        }
        // cerr << el;
        // for(int v : lis) cerr << v << " ";
        // cerr << el;
        ans[eq[i].id] = get(eq[i].r);
    }

    FOR(i, 1, q) cout << ans[i] << el;


}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    #define task "task" 
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    solve();

    return 0;
}

/*

*/

Compilation message (stderr)

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

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