Submission #1181924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181924		al95ireyiz	Osumnjičeni (COCI21_osumnjiceni)	C++20	0 / 110	1097 ms	589824 KiB

Main

// It's the evening of another day. And the end of mine...
#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
// #include<ext/pb_ds/assoc_container.hpp> \
#include<ext/pb_ds/tree_policy.hpp> \
using namespace __gnu_pbds; \
template<class T> \
using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statisticslmode_update>;
#if !defined(ONLINE_JUDGE) and !defined(EVAL)
#include "template/debug.h"
#else
#define d(x...)
#endif
string sp=" ";
#define F ୨୧
#define fr first
#define er erase
#define sc second
#define in insert
#define ll long long
#define pb push_back
#define mkp make_pair
#define qll queue<ll>
#define dqll deque<ll>
#define mll map<ll,ll>
#define vll vector<ll>
#define pll pair<ll,ll>
#define ull unsigned ll
#define mne min_element
#define mxe max_element
#define rs(x)resize(x)
#define vpll vector<pll>
#define vvll vector<vll>
#define pq priority_queue
#define len(x)(ll)x.size()
#define lcm(x,y)x/gcd(x,y)*y
#define all(x)x.begin(),x.end()
#define umll unordered_map<ll,ll>
#define lg2(x)(63ll-__builtin_clzll(x))
#define precision(x)fixed<<setprecision(x)
#define popcnt(x)(ll)__builtin_popcountll(x)
template<typename t1,typename t2>istream&operator>>(istream&is,pair<t1,t2>&x){return is>>x.fr>>x.sc;}
template<typename t1,typename t2>ostream&operator<<(ostream&os,pair<t1,t2>&x){return os<<x.fr<<' '<<x.sc;}
template<typename t1>istream&operator>>(istream&is,vector<t1>&vc){for(t1&j:vc)is>>j;return is;}
template<typename t1>ostream&operator<<(ostream&os,vector<t1>&vc){for(t1&j:vc)os<<j<<sp;return os;}
// #define ll int_fast32_t
// #define ll int_fast64_t
// #pragma GCC optimize("O2")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
const ll INF=1e9;
const ll INFL=1e18;
const ll MOD=1e9+7;
// const ll MOD=998244353;
const ll maxn=1e5+5;
ll n,m,k=0;
inline void prc(){}
// ll tree[4*maxn], lazy[4*maxn];
// void drop(ll l, ll r, ll v){
//     if(lazy[v] == 0) return;
//     tree[v] += lazy[v];
//     if(l!=r){
//         lazy[v<<1] += lazy[v];
//         lazy[v<<1|1] += lazy[v];
//     }
//     lazy[v] = 0;
// }
// void upd(ll _l, ll _r, ll val, ll l=1, ll r=n, ll v=1){
//     drop(l, r, v);
//     bool in = _l <= l and r <= _r;
//     bool ot = _l <= r and l <= _r;
//     if(in){
//         lazy[v] += val;
//         drop(l, r, v);
//         return;
//     }
//     if(ot){
//         ll md = (l+r)>>1;
//         upd(_l, _r, val, l, md, v<<1);
//         upd(_l, _r, val, md+1, r, v<<1);
//         tree[v] = max(tree[v<<1], tree[v<<1|1]);
//     }
// }
// ll get(ll _l, ll _r, ll l=1, ll r=n, ll v=1){
//     drop(l, r, v);
//     bool in = _l <= l and r <= _r;
//     bool ot = _l <= r and l <= _r;
//     if(in){
//         return tree[v];
//     }
//     if(ot){
//         ll md = (l+r)>>1;
//         return max(
//             get(_l, _r, l, md, v<<1),
//             get(_l, _r, md+1, r, v<<1|1)
//         );
//     }
//     return 0;
// }
#define DEF nullptr
struct IMPL{
    IMPL *lt=DEF, *rt=DEF;
    ll l, r, d=0, lazy=0;
    IMPL(ll l, ll r) : l(l), r(r) {}
    void drop(){
        if(lazy == 0) return;
        d += lazy;
        if(l != r){
            ll md = (l+r)>>1;
            if(lt == DEF) lt = new IMPL(l, md);
            if(rt == DEF) rt = new IMPL(md+1, r);
            lt -> lazy += lazy;
            rt -> lazy += lazy;
        }
        lazy = 0;
    }
    void upd(ll _l, ll _r, ll val){
        drop();
        bool in = _l <= l and r <= _r;
        bool ot = _l <= r and l <= _r;
        if(in){
            lazy += val;
            drop();
            return;
        }
        if(ot){
            ll md = (l+r)>>1;
            if(lt == DEF) lt = new IMPL(l, md);
            if(rt == DEF) rt = new IMPL(md+1, r);
            lt -> upd(_l, _r, val);
            rt -> upd(_l, _r, val);
            d = max(lt -> d, rt -> d);
        }
    }
    ll get(ll _l, ll _r){
        drop();
        bool in = _l <= l and r <= _r;
        bool ot = _l <= r and l <= _r;
        if(in){
            return d;
        }
        if(ot){
            ll md = (l+r)>>1;
            return max(
                lt == DEF ? 0 : lt->get(_l, _r),
                rt == DEF ? 0 : rt->get(_l, _r)
            );
        }
        return 0;
    }
} ST(1, INF);
void _(ll&tt){
    cin>>n;
    vpll v(n+1);
    for(ll i=1;i<=n;i++){
        cin>>v[i];
    }
    cin>>m;
    vvll q(m, vll(3));
    for(ll i=0;i<m;i++){
        cin>>q[i][0]>>q[i][1];
        q[i][2] = i;
    }
    sort(all(q));
    vll cv(m);
    ll l=q[0][0], r=q[0][1];
    for(ll i=l;i<=r;i++){
        ST.upd(v[i].fr, v[i].sc, 1);
    }
    cv[q[0][2]] = ST.get(1, INF);
    for(ll i=1;i<m;i++){
        d(q[i], l, r);
        while(q[i][0] > l) ST.upd(v[l].fr, v[l].sc, -1), l++;
        while(q[i][1] < r) ST.upd(v[r].fr, v[r].sc, -1), r--;
        while(q[i][1] > r) r++, ST.upd(v[r].fr, v[r].sc, 1);
        cv[q[i][2]] = ST.get(1, INF);
    }
    for(ll i=0;i<m;i++) cout<<cv[i]<<'\n';
}
signed main(){
    clock_t testcaseruntime=clock();
    cin.tie(0)->sync_with_stdio(0);
    prc();
    ll t=1;
    // cin>>t;
    for(ll tt=1;tt<=t;tt++){
        // cout<<"Case "<<tt<<": ";
        _(tt);
    }
    cerr<<"\n\033[1;31mTime: \033[1;30m"<<(double)(clock()-testcaseruntime)/CLOCKS_PER_SEC<<"\033[1;32m seconds"<<'\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50