Submission #988714

#	Time	Username	Problem	Language	Result	Execution time	Memory
988714		emad234	Fish (IOI08_fish)	C++17	100 / 100	772 ms	34340 KiB

fish

#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<ll,ll>
const ll mxN = 5e5 + 5;
ll mod = 1e9 + 7;
using namespace std;
pii a[mxN];
ll compress[mxN];
ll seg[mxN * 4];
ll mn[mxN];
bool vis[mxN];
ll N,s,e;
ll combine(ll a,ll b) {return ((a * b) % mod);}
void update(ll ind,ll val){
    ind += N;
    seg[ind] += val;
    for(ind /= 2;ind;ind /= 2) seg[ind] = combine(seg[ind * 2],seg[ind * 2 + 1]);
}
ll query(ll l = 1,ll r = N,ll ind = 1){
    if(l > e || r < s) return 1;
    if(l >= s && r <= e) return seg[ind];
    ll md = (l + r)/ 2;
    return combine(query(l,md,ind * 2),query(md + 1,r,ind * 2 + 1));
}
void prllseg(){
    ll ex = 1;
    for(ll i = 1;i < N * 2;i++){
        cout<<seg[i]<<' ';
        if(ex * 2 - 1 == i){
            cout<<'\n';
            ex *= 2;
        }
    }
}
signed main(){
    memset(compress,-1,sizeof compress);
    ll n,k;
    cin >>n>>k>>mod;
    N = exp2(ceil(log2(k)));
    for(ll i = 0;i < n;i++){
        cin >>a[i].F>>a[i].S;
    }
    sort(a,a + n,greater<>());
    ll id = 0;
    for(ll i = 0;i < N;i++) update(i,1);
    for(ll i = 0;i < n;i++){
        if(compress[a[i].S] == -1){
            compress[a[i].S] = id++;
        }a[i].S = compress[a[i].S];
        update(a[i].S,1);
    }
    id = 0;
    ll ans = 0;
    for(ll i = 0;i < n;i++){
        ll num = 1;
        if(vis[a[i].S]) continue;
        vis[a[i].S] = 1;
        while(a[id].F * 2 > a[i].F && id < n){
            update(a[id].S,-1);
            // cout<<a[id].S<<" TEST\n"; 
            mn[a[id].S] = i;
            id++;
        }
        // prllseg();
        if(i == 0){
            ans = seg[1];
            // cout<<a[i].F<<' '<<a[i].S<<'\n';
            // cout<<ans<<'\n';
            continue;
        }
        s = a[i].S + 2,e = N;
        num = combine(query(),num);
        s = a[i].S + 1, e = a[i].S + 1;
        // cout<<mn[a[i].S]<<' '<<a[i].S<<'\n';
        if(mn[a[i].S] == i){
            num = combine(query(),num);
        }else{
            num = combine(query() - 1,num);
            ans += num;
            num = 1;
            s = a[mn[a[i].S]].S + 1,e = a[i].S;
            num = combine(query(),num);
            s = a[i].S + 2,e = N;
            num = combine(num,query());
            // cout<<num<<'\n';
        }
        ans += num;
        ans %= mod;
        // cout<<a[i].F<<' '<<a[i].S<<'\n';
    }
    cout<<ans<<'\n';

}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6
• Subtask 10: 6 / 6
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 7 / 7
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5