Submission #1150241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150241		shjeong	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	516 ms	49988 KiB

matryoshka

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define COMP(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define MOD2 998244353
#define sz(x) (ll)x.size()
typedef __uint128_t lll;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ll, pll> PP;
const ll Lnf = 2e18;
const ll inf = 1e9;
ll n, q;
struct segtree{
    vector<ll> tree;
    segtree(): tree(1616161){}
    void upd(ll node, ll s, ll e, ll i, ll d){
        if(e<i or i<s)return;
        if(s==e)tree[node]=max(tree[node],d);
        else{
            ll mid = s+e>>1;
            upd(node<<1,s,mid,i,d);
            upd(node<<1|1,mid+1,e,i,d);
            tree[node]=max(tree[node<<1],tree[node<<1|1]);
        }
    }
    ll query(ll node, ll s, ll e, ll l, ll r){
        if(e<l or r<s)return 0;
        if(l<=s and e<=r)return tree[node];
        ll mid = s+e>>1; return max(query(node<<1,s,mid,l,r),query(node<<1|1,mid+1,e,l,r));
    }
} seg;
ll ans[202020];
vector<pll> p[404040];  //[y,isquery]
int main(){
    fast;
    cin>>n>>q;
    vector<pll> v(n); vector<ll> cpx, cpy;
    for(auto &[a,b] : v){
        cin>>a>>b; cpx.push_back(a); cpy.push_back(b);
    }
    vector<pll> Q(q);
    for(auto &[a,b] : Q){
        cin>>a>>b; cpx.push_back(a); cpy.push_back(b);
    }
    sort(all(cpx)); COMP(cpx);
    sort(all(cpy)); COMP(cpy);
    for(int i = 0 ; i < n ; i++){
        ll x = lower_bound(all(cpx),v[i].first)-cpx.begin()+1;
        ll y = lower_bound(all(cpy),v[i].second)-cpy.begin()+1;
        y = sz(cpy)+1-y;
        p[x].push_back({y,0});
//        cout<<x<<" "<<y<<endl;
    }
    for(int i = 0 ; i < q ; i++){
        ll x = lower_bound(all(cpx),Q[i].first)-cpx.begin()+1;
        ll y = lower_bound(all(cpy),Q[i].second)-cpy.begin()+1;
        y = sz(cpy)+1-y;
        p[x].push_back({y,-(i+1)});
    }
    for(int x = sz(cpx) ; x >= 1 ; x--){
        sort(rll(p[x]));
        for(auto [y,id] : p[x]){
//            cout<<x<<" "<<y<<" "<<id<<endl;
            if(id==0){
                seg.upd(1,1,sz(cpy),y,seg.query(1,1,sz(cpy),y,sz(cpy))+1);
            }
            else{
                id=-id;
                ans[id] = seg.query(1,1,sz(cpy),y,sz(cpy));
            }
        }
    }
    for(int i = 1 ; i <= q ; i++)cout<<ans[i]<<"\n";
}

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