Submission #1096495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096495		coldbr3w	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	856 ms	93764 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n,q;
ll l[N], r[N];
ll up[N][20];
struct segment_tree{
    ll n;
    vector<ll>st, lz;
    void init(ll _n){
        n = _n;
        st.clear(); st.resize(4 * n + 10, 0);
        lz.clear(); lz.resize(4 * n + 10, 0);
    }
    void down(ll id, ll l, ll r){
        st[id] += lz[id];
        if(l != r) lz[2 * id] += lz[id], lz[2 * id + 1] += lz[id];
        lz[id] = 0;
    }
    void update(ll id, ll l, ll r, ll left, ll right, ll val){
        down(id, l, r);
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            lz[id] += val;
            down(id, l, r);
            return;
        }
        ll mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, val);
        update(2 * id + 1, mid + 1, r, left, right, val);
        st[id] = max(st[2 * id], st[2 * id + 1]);
    }
    ll get(ll id, ll l, ll r, ll left, ll right){
        down(id, l, r);
        if(l > right || r < left) return 0;
        if(left <= l && r <= right) return st[id];
        ll mid = (l + r) / 2;
        return max(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
    }
    void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
    ll get(ll l, ll r){return get(1,1,n,l,r);}
} st;
void to_thic_cau(){
    cin >> n;
    vector<ll>v;
    for(int i = 1; i <= n;i++){
        cin >> l[i] >> r[i];
        v.pb(l[i]); v.pb(r[i]);
    }
    map<ll,ll>mp;
    sort(all(v)); v.erase(unique(all(v)), v.end());
    for(int i = 0; i < v.size();i++) mp[v[i]] = i + 1;
    for(int i = 1; i <= n;i++) mp[v[i]] = i + 1;
    st.init(2 * n);
    ll j = n;
    for(int i = n; i >= 1;i--){
        l[i] = mp[l[i]], r[i] = mp[r[i]];
        st.update(l[i], r[i], 1);
        while(st.get(1, 2 * n) >= 2){
            st.update(l[j], r[j], -1);
            j--;
        }
        up[i][0] = j + 1;
    }
    for(int j = 1; j <= 19;j++){
        for(int i = 1; i <= n;i++) up[i][j] = up[up[i][j-1]][j-1];
    }
    cin >> q;
    while(q--){
        ll p,q; cin >> p >> q;
        ll res = 1;
        for(int i = 19; i >= 0;i--){
            if(up[p][i] <= q && up[p][i]){
                p = up[p][i];
                res += (1 << i);
            }
        }
        cout << res << "\n";
    }
}

signed main()   
{  
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

Compilation message (stderr)

Main.cpp: In function 'void to_thic_cau()':
Main.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0; i < v.size();i++) mp[v[i]] = i + 1;
      |                    ~~^~~~~~~~~~

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