oj.uz

Submission #221484

# Submission time Handle Problem Language Result Execution time Memory
221484 2020-04-10T09:47:14 Z anonymous Fish (IOI08_fish) C++14
100 / 100
 645 ms 52188 KB 
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#define MAXN 500005
#define fi first
#define se second
using namespace std;
int F, K, M, B[MAXN], Pos[MAXN], Ans;
bool done[MAXN];
pair<int,int> Fish[MAXN];
vector<int> S[MAXN];
vector<pair<int,int> > Ord;

class Segtree {
    int ST[MAXN*2];
public:
    void init() {
        for (int i=1; i<=2*K; i++) {
            ST[i] = 1;
        }
    }
    void upd(int p) {
        p+=K;
        for (ST[p] = (ST[p] + 1) % M; p > 1; p>>=1) {
            ST[p>>1] = (ST[p] * ST[p^1]) % M;
        }
    }
    int ask(int l, int r) {  // product on interval [l, r]
        if (l > r) {return(1);}
        int res = 1;
        r+=1;
        for (l += K, r += K; l < r; l >>= 1, r >>= 1) {
            if (l&1) res = (res * ST[l++])%M;
            if (r&1) res = (res * ST[--r])%M;
        }
        return res;
    }
} ST;

int FindRange(int t) {
    int thresh = *upper_bound(S[t].begin(), S[t].end(), B[t]/2), lo = -1, hi = K;
    while (lo + 1 != hi) {
        int mid = (lo + hi) >> 1;
        if (2*thresh <= Ord[mid].first) {hi = mid;}
        else {lo = mid;}
    }
    return(lo); //returns Pos of last not greater
}

int main() {
    //freopen("fishin.txt","r",stdin);
    scanf("%d\n%d\n%d",&F,&K,&M);
    for (int i=1; i<=F; i++) {
        scanf("%d %d",&Fish[i].fi, &Fish[i].se);
    }
    sort(Fish+1, Fish+F+1);
    ST.init()  ;
    for (int i=1; i<=F; i++) {
        B[Fish[i].se] = Fish[i].fi;
        S[Fish[i].se].push_back(Fish[i].fi);
    }

    for (int i=1; i<=K; i++) {
        Ord.push_back({B[i], i});
    }
    sort(Ord.begin(), Ord.end());
    for (int i=0; i<K; i++) {
        Pos[Ord[i].second] = i;
    }
    int pt = 1;
    for (int i=1; i<=F; i++) {
        while (pt <= F && Fish[pt].fi*2 <= Fish[i].fi) {
            ST.upd(Pos[Fish[pt].se]);
            pt++;
        }
        if (!done[Fish[i].se] && Fish[i].fi == B[Fish[i].se]) {
            done[Fish[i].se] = true;
            int NonMax = ((ST.ask(Pos[Fish[i].se], Pos[Fish[i].se]) - 1) *  ST.ask(0, Pos[Fish[i].se]-1)) % M;

            int Max = (ST.ask(0, Pos[Fish[i].se]-1) * ST.ask(Pos[Fish[i].se]+1, FindRange(Fish[i].se)))%M;
            Ans = (Ans + Max + NonMax) %M;
        }
    }
    printf("%d", Ans);
}

Compilation message

fish.cpp: In function 'int main()':
fish.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n%d\n%d",&F,&K,&M);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&Fish[i].fi, &Fish[i].se);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12092 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 214 ms 20216 KB Output is correct

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 17144 KB Output is correct
2 Correct 117 ms 17632 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 158 ms 18740 KB Output is correct
2 Correct 264 ms 20224 KB Output is correct
3 Correct 243 ms 25576 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 20600 KB Output is correct
2 Correct 264 ms 26232 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 18728 KB Output is correct
2 Correct 255 ms 20752 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 21704 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 20720 KB Output is correct
2 Correct 323 ms 31216 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 26480 KB Output is correct
2 Correct 326 ms 28016 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 27372 KB Output is correct
2 Correct 388 ms 31220 KB Output is correct
3 Correct 398 ms 35568 KB Output is correct
4 Correct 390 ms 31088 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 29160 KB Output is correct
2 Correct 489 ms 51296 KB Output is correct
3 Correct 633 ms 52188 KB Output is correct
4 Correct 645 ms 46564 KB Output is correct