Submission #221449

#TimeUsernameProblemLanguageResultExecution timeMemory
221449anonymousFish (IOI08_fish)C++14
4 / 100
3086 ms27500 KiB
#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 { //0 indexed int ST[MAXN*2]; public: void init() { for (int i=0; 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] 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 = S[t][ST.ask(Pos[t], Pos[t])-1], lo = 0, hi = K-1; 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); M= 1000; 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 (stderr)

fish.cpp: In function 'int main()':
fish.cpp:52: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);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...