Submission #1306300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306300		dex111222333444555	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	125 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 Q{
    int low, high, id;
    Q(int _low = 0, int _high = 0, int _id = 0):
        low(_low), high(_high), id(_id) {};

    bool operator<(const Q &other){
        return low > other.low;
    }
};

int numVal, numQuery, res[MAXN];
ii val[MAXN];
Q 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].low >> query[q].high, 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);
}

void solve(){
    vector<int> lis;
    sort(val + 1, val + 1 + numVal, cmp);
    sort(query + 1, query + 1 + numQuery);

    int j = 1;
    for(int i = 1; i <= numQuery; i++){
        while(j <= numVal && val[j].fi >= query[i].low){
            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++;
        }
        res[query[i].id] = upper_bound(all(lis), query[i].high) - begin(lis);
    }

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

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