Submission #659067

#	Time	Username	Problem	Language	Result	Execution time	Memory
659067		qwerasdfzxcl	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	347 ms	22780 KiB

matryoshka

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Seg{
    int tree[800800], sz;
    void init(int n){sz = n;}
    void update(int p, int x){
        p += sz;
        tree[p] = max(tree[p], x);
        for (p>>=1;p;p>>=1) tree[p] = max(tree[p<<1], tree[p<<1|1]);
    }
    int query(int r){
        int l = 0, ret = 0;
        for (l+=sz, r+=sz+1;l<r;l>>=1, r>>=1){
            if (l&1) ret = max(ret, tree[l++]);
            if (r&1) ret = max(ret, tree[--r]);
        }
        return ret;
    }
}tree;
struct Data{
    int x, y, isq, i;
    Data(){}
    Data(int _x, int _y, int _q, int _i): x(_x), y(_y), isq(_q), i(_i) {}
    bool operator < (const Data &D){
        if (x==D.x && y==D.y) return isq < D.isq;
        if (x==D.x) return y < D.y;
        return x > D.x;
    }
};
vector<Data> D;
int ans[200200];
vector<int> Y;

void compress(vector<int> &a){sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end());}
int getidx(const vector<int> &a, int x){return lower_bound(a.begin(), a.end(), x) - a.begin();}

int main(){
    Y.push_back(0);

    int n, q;
    scanf("%d %d", &n, &q);
    for (int i=1;i<=n;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        Y.push_back(y);
        D.emplace_back(x, y, 0, 0);
    }

    for (int i=1;i<=q;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        Y.push_back(y);
        D.emplace_back(x, y, 1, i);
    }

    compress(Y);
    tree.init(Y.size());
    sort(D.begin(), D.end());

    for (auto &[x, y, isq, i]:D){
        y = getidx(Y, y);
        if (isq) {ans[i] = tree.query(y); continue;}
        tree.update(y, tree.query(y) + 1);
    }

    for (int i=1;i<=q;i++) printf("%d\n", ans[i]);
    return 0;
}

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
matryoshka.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
matryoshka.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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