Submission #988706

#	Time	Username	Problem	Language	Result	Execution time	Memory
988706		emad234	Fish (IOI08_fish)	C++17	0 / 100	567 ms	27728 KiB

fish

#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<ll,ll>
const int mxN = 5e5 + 5;
int mod = 1e9 + 7;
using namespace std;
pii a[mxN];
int compress[mxN];
ll seg[mxN * 4];
ll mn[mxN];
bool vis[mxN];
int N,s,e;
ll combine(ll a,ll b) {return ((a * b) % mod);}
void update(int ind,int val){
    ind += N;
    seg[ind] += val;
    for(ind /= 2;ind;ind /= 2) seg[ind] = combine(seg[ind * 2],seg[ind * 2 + 1]);
}
ll query(int l = 1,int r = N,int ind = 1){
    if(l > e || r < s) return 1;
    if(l >= s && r <= e) return seg[ind];
    int md = (l + r)/ 2;
    return combine(query(l,md,ind * 2),query(md + 1,r,ind * 2 + 1));
}
void printseg(){
    int ex = 1;
    for(int 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);
    int n,k;
    cin >>n>>k>>mod;
    N = exp2(ceil(log2(k)));
    for(int i = 0;i < n;i++){
        cin >>a[i].F>>a[i].S;
    }
    sort(a,a + n,greater<>());
    int id = 0;
    for(int i = 0;i < N;i++) update(i,1);
    for(int 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(int i = 0;i < n;i++){
        int 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++;
        }
        // printseg();
        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(),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: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5