Submission #592126

#TimeUsernameProblemLanguageResultExecution timeMemory
592126Do_you_copyBoat (APIO16_boat)C++17
0 / 100
1 ms468 KiB
#include <bits/stdc++.h> #define taskname "test" #define fi first #define se second #define pb push_back #define faster ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; using ll = long long; using pii = pair <int, int>; using pil = pair <int, ll>; using pli = pair <ll, int>; using pll = pair <ll, ll>; using ull = unsigned ll; mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count()); ll min(const ll &a, const ll &b){ return (a < b) ? a : b; } ll max(const ll &a, const ll &b){ return (a > b) ? a : b; } const ll Mod = 1000000009; //const ll Mod2 = 999999999989; //only use when required const int maxN = 5e2 + 1; int n; ll bit[maxN * 2]; vector <int> v; struct TBoat{ int l, r; }; TBoat a[maxN]; ll dp[maxN * 2]; ll update(int x, ll val){ for (; x <= v.size(); x += x & -x){ bit[x] += val; bit[x] %= Mod; } } ll get(int x){ ll ans = 0; for (; x; x -= x & -x){ ans += bit[x]; ans %= Mod; } return ans; } void Init(){ cin >> n; for (int i = 1; i <= n; ++i){ cin >> a[i].l >> a[i].r; v.pb(a[i].l); v.pb(a[i].r); } sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); for (int i = 1; i <= n; ++i){ int from = lower_bound(v.begin(), v.end(), a[i].l) - v.begin(); int to = lower_bound(v.begin(), v.end(), a[i].r) - v.begin(); for (int j = from; j < to; ++j){ dp[j] = (get(j) + 1) * (v[j + 1] - v[j]) % Mod; } dp[to] = get(to + 1) + 1; for (int j = from; j <= to; ++j){ update(j + 1, dp[j]); } } cerr << get(v.size()); } int main(){ if (fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); //freopen(taskname".out", "w", stdout); } faster; ll tt = 1; //cin >> tt; while (tt--){ Init(); } }

Compilation message (stderr)

boat.cpp: In function 'll update(int, ll)':
boat.cpp:40:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (; x <= v.size(); x += x & -x){
      |            ~~^~~~~~~~~~~
boat.cpp:44:1: warning: no return statement in function returning non-void [-Wreturn-type]
   44 | }
      | ^
boat.cpp: In function 'int main()':
boat.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...