Submission #217783

#	Time	Username	Problem	Language	Result	Execution time	Memory
217783		mhy908	Fish (IOI08_fish)	C++14	100 / 100	797 ms	53496 KiB

fish

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int n, k;
LL m, ans;
pii arr[500010];
struct SEGMENT_TREE{
    LL tree[2000010];
    void update(int point, int s, int e, int num, LL val){
        if(s==e){
            tree[point]+=val;
            tree[point]%=m;
            return;
        }
        if(num<=(s+e)/2)update(point*2, s, (s+e)/2, num, val);
        else update(point*2+1, (s+e)/2+1, e, num, val);
        tree[point]=tree[point*2]*tree[point*2+1]%m;
    }
    LL query(int point, int s, int e, int a, int b){
        if(a<=s&&e<=b)return tree[point];
        if(e<a||s>b)return 1ll;
        return query(point*2, s, (s+e)/2, a, b)*query(point*2+1, (s+e)/2+1, e, a, b)%m;
    }
}seg;

int change[500010], maxnum[500010], cov[500010];
vector<int> vc[500010];
bool ismax[500010];

int main(){
    scanf("%d %d %lld", &n, &k, &m);
    for(int i=1; i<=k; i++)seg.update(1, 1, k, i, 1);
    for(int i=1; i<=n; i++)scanf("%d %d", &arr[i].F, &arr[i].S);
    sort(arr+1, arr+n+1);
    int tmp=k;
    for(int i=n; i>=1; i--){
        if(!change[arr[i].S]){
            change[arr[i].S]=tmp--;
            maxnum[change[arr[i].S]]=arr[i].F;
            vc[change[arr[i].S]].pb(arr[i].F);
            ismax[i]=true;
        }
        else vc[change[arr[i].S]].pb(arr[i].F);
    }
    for(int i=1; i<=k; i++)reverse(all(vc[i]));
    int pv=1;
    for(int i=1; i<=n; i++){
        if(!ismax[i])continue;
        for(; pv<i; pv++){
            if(arr[pv].F*2>arr[i].F)break;
            cov[change[arr[pv].S]]++;
            seg.update(1, 1, k, change[arr[pv].S], 1);
        }
        int temp=lower_bound(maxnum+1, maxnum+k+1, vc[change[arr[i].S]][cov[change[arr[i].S]]]*2)-maxnum;
        ans+=seg.query(1, 1, k, 1, change[arr[i].S]);
        ans%=m;
        ans+=seg.query(1, 1, k, 1, change[arr[i].S]-1)*(seg.query(1, 1, k, change[arr[i].S]+1, temp-1)+m-1)%m;
        ans%=m;
    }
    printf("%lld", ans);
}

Compilation message (stderr)

fish.cpp: In function 'int main()':
fish.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %lld", &n, &k, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:41:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=n; i++)scanf("%d %d", &arr[i].F, &arr[i].S);
                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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