Submission #1288602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288602		dex111222333444555	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	121 ms	7424 KiB

matryoshka

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define all(v) begin(v), end(v)
using namespace std;
const int MAXN = 2e5 + 5;

struct Q{
    int X, Y, id;
    Q(int _X = 0, int _Y = 0, int _id = 0):
        X(_X), Y(_Y), id(_id) {};
};

int numVal, numQuery, ans[MAXN];
ii val[MAXN];
Q query[MAXN];

bool cmp(const Q &a, const Q &b){
    return a.X > b.X || (a.X == b.X && a.Y > b.Y);
}

bool cmp2(const ii &a, const ii &b){
    return (a.first > b.first || (a.first == b.first && a.second < b.second));
}

void input(){
    cin >> numVal >> numQuery;
    for(int i = 1; i <= numVal; i++) cin >> val[i].fi >> val[i].se;
    for(int i = 1; i <= numQuery; i++) cin >> query[i].X >> query[i].Y, query[i].id = i;
}

void solve(){
    sort(val + 1, val + 1 + numVal, cmp2);
    sort(query + 1, query + 1 + numQuery, cmp);
    vector<int> lis;
    int j = 1;
    for(int i = 1; i <= numQuery; i++){
        while(val[j].fi >= query[i].X){
            vector<int>::iterator it =  upper_bound(all(lis), val[j].se);
            if (it == end(lis)) lis.push_back(val[j].se);
            else *it = val[j].se;
            j++;
        }
        int pos = upper_bound(all(lis), query[i].Y) - begin(lis);
        ans[query[i].id] = pos;
    }
    for(int q = 1; q <= numQuery; q++) cout << ans[q] << '\n';
}

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

Compilation message (stderr)

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

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