Submission #1192490

#TimeUsernameProblemLanguageResultExecution timeMemory
1192490GrayBoat (APIO16_boat)C++20
9 / 100
4 ms328 KiB
#include <algorithm> #include <bits/stdc++.h> #include <cassert> #include <vector> using namespace std; #define ll long long #define ull unsigned long long #define ld long double #define ff first #define ss second #define ln "\n" #define mp make_pair #define pb push_back #define INF (ll)1e18 ll MOD = 1e9+7; void solve(){ ll n; cin >> n; vector<pair<ll, ll>> a(n); vector<ll> pos; for (ll i=0; i<n; i++){ cin >> a[i].ff >> a[i].ss; pos.push_back(a[i].ff); pos.push_back(a[i].ss); } sort(pos.begin(), pos.end()); pos.erase(unique(pos.begin(), pos.end()), pos.end()); ll pn=pos.size(); vector<ll> dp(pn+1); dp[0]=1; vector<ll> pref(pn+1, 1); ll res=0; for (ll i=0; i<n; i++){ ll l = lower_bound(pos.begin(), pos.end(), a[i].ff)-pos.begin()+1; ll r = lower_bound(pos.begin(), pos.end(), a[i].ss)-pos.begin()+1; ll cres=0; for (ll j=r; j>=l; j--){ dp[j]+=pref[j-1]; dp[j]%=MOD; cres+=pref[j-1]; cres%=MOD; } res+=cres; res%=MOD; for (ll j=1; j<=pn; j++) pref[j]=(pref[j-1]+dp[j])%MOD; } cout << res << ln; } /* 15-7=6+6-x 12 TLILII TLILTII TLITLTII TLITLTLII */ int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL auto start = chrono::high_resolution_clock::now(); #endif ll testc=1; // cin >> testc; for (ll __c=1; __c<=testc; __c++) solve(); #ifdef LOCAL auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start); cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...