oj.uz

Submission #217783

# Submission time Handle Problem Language Result Execution time Memory
217783 2020-03-30T18:06:58 Z mhy908 Fish (IOI08_fish) C++14
100 / 100
 797 ms 53496 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 12 ms 12160 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Correct 221 ms 24568 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12208 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 17456 KB Output is correct
2 Correct 128 ms 18804 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12288 KB Output is correct
2 Correct 14 ms 12288 KB Output is correct
3 Correct 14 ms 12288 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 20600 KB Output is correct
2 Correct 270 ms 25196 KB Output is correct
3 Correct 265 ms 25832 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 25208 KB Output is correct
2 Correct 261 ms 26232 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 21176 KB Output is correct
2 Correct 272 ms 26096 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 25464 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 27640 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 25464 KB Output is correct
2 Correct 345 ms 31996 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 34296 KB Output is correct
2 Correct 364 ms 30328 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 33144 KB Output is correct
2 Correct 437 ms 32376 KB Output is correct
3 Correct 476 ms 37100 KB Output is correct
4 Correct 450 ms 32476 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 37496 KB Output is correct
2 Correct 776 ms 53496 KB Output is correct
3 Correct 627 ms 52556 KB Output is correct
4 Correct 797 ms 50044 KB Output is correct