Submission #1011241

#TimeUsernameProblemLanguageResultExecution timeMemory
1011241vjudge1Fish (IOI08_fish)C++17
100 / 100
625 ms65536 KiB
#include <bits/stdc++.h> //#include<ext/pb_ds/assoc_container.hpp> //#include<ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef unsigned int ui; #define ii pair<int,int> #define pll pair<ll,ll> #define vi vector<int> #define vii vector<ii> #define vll vector<ll> #define vpll vector<pll> #define matrix vector<vi> #define matrixLL vector<vll> #define vs vector<string> #define vui vector<ui> #define msi multiset<int> #define mss multiset<string> #define si set<int> #define ss set<string> #define PB push_back #define PF push_front #define PPB pop_back #define PPF pop_front #define X first #define Y second #define MP make_pair #define FOR(i, a, b) for (int i = int(a); i < int(b); i++) #define REP(i, n) FOR(i, 0, n) #define all(x) (x).begin(), (x).end() const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1}; const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1}; const string abc="abcdefghijklmnopqrstuvwxyz"; const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const ld pi = 3.14159265; int mod = 1e9 + 7; const int MOD = 1e9 + 7; const int MAXN = 1e6 + 7; const int inf = mod; const ll INF = 1e18; const ll zero = ll(0); const int logo = 19; const int off = 1 << logo; const int trsz = off << 1; vii arr; int gdid[MAXN], seg[trsz], pos[MAXN], kol[MAXN]; void update(int x, int val){ x += off; seg[x] = (seg[x] + val + mod) % mod; for(x /= 2; x; x /= 2) seg[x] = ((ll)seg[x * 2] * (ll)seg[x * 2 + 1]) % mod; } ll query(int x, int lo, int hi, int a, int b){ if(lo >= b or hi <= a) return 1; if(lo >= a and hi <= b) return seg[x]; int mid = (lo + hi) / 2; return ((ll)query(x * 2, lo, mid, a, b) * (ll)query(x * 2 + 1, mid, hi, a, b)) % mod; } vi c; vpll boje; vi siz[MAXN]; void solve(){ fill(seg, seg + trsz, 1); fill(gdid, gdid + MAXN - 1, -1); int n, k, m; cin >> n >> k >> mod; arr.resize(n); REP(i, n) cin >> arr[i].X >> arr[i].Y; sort(all(arr)); for(int i = n - 1; i >= 0; i--){ siz[arr[i].Y].PB(arr[i].X); if(gdid[arr[i].Y] == -1) gdid[arr[i].Y] = i, c.PB(arr[i].Y), boje.PB({arr[i].X, i}); } reverse(all(c)); for(int i=0; i<c.size(); i++) pos[c[i]] = i, reverse(all(siz[c[i]])); for(int i=0; i<n; i++) update(pos[arr[i].Y], 1); sort(all(boje)); boje.PB({INF, inf}); int ans = 0; int R = n - 1; for(int i = n - 1; i >= 0; i--){ while(R >= 0 and arr[R].X * 2 > arr[i].X) update(pos[arr[R].Y], -1), R--; if(gdid[arr[i].Y] != i) continue; if(i == n - 1){ REP(i, k + 1) kol[i] = seg[i + off]; } ans = (ans + query(1, 0, off, 0, pos[arr[i].Y] + 1)) % mod; int prv = *lower_bound(all(siz[arr[i].Y]), arr[i].X / 2 + 1); int poz = lower_bound(all(boje), MP((ll)prv * 2, (ll)-inf)) - boje.begin(); if(pos[arr[i].Y] + 1 < poz){ int val = ((ll)query(1, 0, off, 0, pos[arr[i].Y]) * (ll)(((ll)query(1, 0, off, pos[arr[i].Y] + 1, poz) - 1 + mod) % mod)) % mod; ans = (ans + val) % mod; } } cout << ans << "\n"; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t=1; //cin >> t; while(t--)solve(); return 0; }

Compilation message (stderr)

fish.cpp: In function 'void solve()':
fish.cpp:88:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for(int i=0; i<c.size(); i++) pos[c[i]] = i, reverse(all(siz[c[i]]));
      |               ~^~~~~~~~~
fish.cpp:77:12: warning: unused variable 'm' [-Wunused-variable]
   77 |  int n, k, m;
      |            ^
#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...