Submission #1300520

#TimeUsernameProblemLanguageResultExecution timeMemory
1300520tte0Osumnjičeni (COCI21_osumnjiceni)C++20
0 / 110
1096 ms7984 KiB
// Author: Teoman Ata Korkmaz
#include <bits/stdc++.h> 
using namespace std;
///////////////////////////////////////////////////////////
int n,q;
vector<tuple<int,int>> v;

inline int solve(int l,int r){
    //cerr<<"l,r: "<<l<<" "<<r<<endl;
    vector<tuple<int,int>> v(::v.begin()+l,::v.begin()+r+1);
    sort(v.begin(),v.end(),[](const auto& a,const auto& b){
        const auto [al,ar]=a;
        const auto [bl,br]=b;
        return ar!=br?ar<br:al>bl;
    });

    int ans=0;
    map<int,int> mp;
    for(const auto [l,r]:v){
        //cerr<<l<<" "<<r<<endl;
        auto it=mp.lower_bound(l);
        if(it!=mp.begin()){
            //cerr<<"what"<<endl;
            it--;
            assert((*it).second>0);
            if(!(--((*it).second)))mp.erase(it);
        }
        else ans++;
        mp[r]++;
    }

    return ans;
}

signed main(void){
    cin>>n;
    v.resize(n);
    for(auto& [l,r]:v){cin>>l>>r;}
    cin>>q;

    while(q--){
        static int x,y;
        cin>>x>>y;
        x--,y--;
        cout<<solve(x,y)<<endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...