Submission #433891

#TimeUsernameProblemLanguageResultExecution timeMemory
433891someoneBoat (APIO16_boat)C++14
9 / 100
690 ms524292 KiB
#include <bits/stdc++.h> using namespace std; struct Val { int i, val; }; const int M = 1 << 21, N = 2 * M, T = 500, MOD = 1e9 + 7; int node[N]; int a[T], b[T]; vector<Val> p; int getSum(int i) { if(i == 1) return 0; int sum = getSum(i/2); if(i % 2 == 1) sum += node[i-1]; return sum % MOD; } void add(int i, int val) { if(i == 0) return; node[i] = (node[i] + val) % MOD; add(i/2, val); } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; int sum = 0; for(int i = 0; i < n; i++) { cin >> a[i] >> b[i]; sum += b[i] - a[i]; } if(sum > M) return 0; for(int i = 0, x = 0; i < n; i++) for(int j = b[i]; j >= a[i]; j--, x++) p.push_back({x, j}); sort(p.begin(), p.end(), [](Val v1, Val v2) { return v1.val < v2.val; }); int pre = p[0].val; p[0].val = 1; for(int i = 1; i < n; i++) { bool eq = (pre != p[i].val); pre = p[i].val; p[i].val = p[i-1].val + eq; } sort(p.begin(), p.end(), [](Val v1, Val v2) { return v1.i < v2.i; }); sum = 0; for(Val v: p) { int val = getSum(v.val + M) + 1; add(v.val + M, val); sum = (sum + val) % MOD; } cout << sum; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...