Submission #1305627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305627		dex111222333444555	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	116 ms	7320 KiB

matryoshka

#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second

using namespace std;

const int MAXN = 2e5 + 5;

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

int numVal, numQuery, res[MAXN];
ii val[MAXN];
queries query[MAXN];

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

bool cmp(const ii &a, const ii &b){
    return (a.fi > b.fi) || (a.fi == b.fi && a.se < b.se);
}

bool cmpQ(const queries &a, const queries &b){
    return (a.X > b.X);
}

void solve(){
    sort(val + 1, val + 1 + numVal, cmp);
    sort(query + 1, query + 1 + numQuery, cmpQ);

    int j = 1;
    vector<int> lis;
    for(int q = 1; q <= numQuery; q++){
        while(val[j].fi >= query[q].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[q].Y) - begin(lis);
        res[query[q].id] = pos;
    }

    for(int q = 1; q <= numQuery; q++) cout << res[q] << '\n';
}

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

Compilation message (stderr)

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

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