# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
777676 | 2023-07-09T12:55:51 Z | salmon | Fish (IOI08_fish) | C++14 | 614 ms | 65536 KB |
#include <bits/stdc++.h> using namespace std; int N,M; int mod; int l,h; vector<pair<int,int>> v; vector<pair<int,int>> oh; int mapping[500100]; bool o[500100]; int iv[500100]; struct node{ int s,e; long long int v; node *l,*r; node(int S, int E){ s = S; e = E; int m = (s + e)/2; v = 1; if(s != e){ l = new node(s,m); r = new node(m + 1, e); } } void update(int i, int k){ if(s == e){ v += k; v %= mod; return; } int m = (s + e)/2; if(i <= m){ l -> update(i,k); } else{ r -> update(i,k); } v = (l -> v * r -> v) % mod; } long long int query(int S, int E){ if(E < S) return 1; if(S <= s && e <= E){ return v; } int m = (s + e)/2; long long int V = 1; if(S <= m){ V *= l -> query(S,E); } if(m < E){ V *= r -> query(S,E); } return V % mod; } }*lroot; int main(){ scanf(" %d",&N); scanf(" %d",&M); scanf(" %d",&mod); int next[500100]; for(int i = 1; i <= M; i++){ next[i] = -1; } for(int i = 0; i < N; i++){ scanf(" %d",&l); scanf(" %d",&h); v.push_back(make_pair(l,h)); } sort(v.begin(),v.end(),greater<pair<int,int>>()); for(int i = 0; i <= M; i++){ o[i] = true; } for(int i = 0; i < v.size(); i++){ if(o[v[i].second]){ oh.push_back(v[i]); o[v[i].second] = false; iv[v[i].second] = v.size() - 1 - i; } if(v[i].first * 2 > v[v.size() - 1 - iv[v[i].second]].first ){ next[v[i].second] = v[i].first; } } lroot = new node(0,M); int it = 0; int it1 = 0; reverse(oh.begin(),oh.end()); for(int i = 0; i < oh.size(); i++){ mapping[oh[i].second] = i; } reverse(oh.begin(),oh.end()); reverse(v.begin(),v.end()); long long int bigans = 0; M = oh.size(); for(int i = 0; i < N; i++){ while(it != N && v[i].first >= v[it].first * 2){ lroot -> update(mapping[v[it].second], 1); it++; } if(i == iv[oh.back().second]){ bigans += lroot -> query(0,M - oh.size()); bigans %= mod; int e = lower_bound(oh.begin(),oh.end(),make_pair(next[v[i].second] * 2 - 1, 1100100100),greater<pair<int,int>>()) -> second; bigans += (lroot -> query(0,mapping[v[i].second] - 1)) * (lroot -> query(mapping[v[i].second] + 1, mapping[e] ) - 1 + mod); bigans %= mod; oh.pop_back(); } } printf("%d",bigans); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2260 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2260 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2264 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2264 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2272 KB | Output is correct |
2 | Correct | 2 ms | 2260 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2260 KB | Output is correct |
2 | Correct | 144 ms | 12336 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2260 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 2276 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 64 ms | 6324 KB | Output is correct |
2 | Correct | 78 ms | 7480 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 2556 KB | Output is correct |
2 | Correct | 3 ms | 2516 KB | Output is correct |
3 | Correct | 4 ms | 2532 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 99 ms | 10188 KB | Output is correct |
2 | Correct | 178 ms | 13120 KB | Output is correct |
3 | Correct | 168 ms | 13056 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 161 ms | 12516 KB | Output is correct |
2 | Correct | 171 ms | 13476 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 93 ms | 10348 KB | Output is correct |
2 | Correct | 177 ms | 13936 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 172 ms | 13428 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 193 ms | 15448 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 162 ms | 17060 KB | Output is correct |
2 | Correct | 191 ms | 25004 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 342 ms | 29488 KB | Output is correct |
2 | Correct | 277 ms | 25840 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 292 ms | 27648 KB | Output is correct |
2 | Correct | 347 ms | 25004 KB | Output is correct |
3 | Correct | 331 ms | 34928 KB | Output is correct |
4 | Correct | 300 ms | 24972 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 442 ms | 36264 KB | Output is correct |
2 | Correct | 559 ms | 65536 KB | Output is correct |
3 | Correct | 460 ms | 65536 KB | Output is correct |
4 | Correct | 614 ms | 58484 KB | Output is correct |