제출 #142597

#제출 시각아이디문제언어결과실행 시간메모리
14259712tqianBoat (APIO16_boat)C++14
9 / 100
55 ms6184 KiB
#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize ("O3") #pragma GCC target ("sse4") #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; const double PI = 4 * atan(1); #define sz(x) (int)(x).size() #define ll long long #define ld long double #define mp make_pair #define pb push_back #define eb emplace_back #define pii pair <int, int> #define vi vector<int> #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define vpi vector<pair<int, int>> #define vpd vector<pair<double, double>> #define pd pair<double, double> #define f0r(i,a) for(int i=0;i<a;i++) #define f1r(i,a,b) for(int i=a;i<b;i++) #define trav(a, x) for (auto& a : x) void fast_io(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); } void io(string taskname){ string fin = taskname + ".in"; string fout = taskname + ".out"; const char* FIN = fin.c_str(); const char* FOUT = fout.c_str(); freopen(FIN, "r", stdin); freopen(FOUT, "w", stdout); fast_io(); } const ll MOD = 1e9 + 7; const int MAX = 505; vector<pair<ll, ll>> bounds; vector<pair<ll, ll>> ranges; ll dp[MAX][MAX*3]; vi possible[MAX]; template<class T, int SZ> struct Seg { // SZ should be power of 2 T ID = 0; // comb(ID,b) must equal b T comb(T a, T b) { return (a+b)%MOD; } // easily change this to min or max T seg[2*SZ]; Seg() { memset(seg,0,sizeof seg); } void upd(int p, T value) { // set value at position p seg[p += SZ] = value; for (p /= 2; p; p /= 2) seg[p] = comb(seg[2*p],seg[2*p+1]); } T query(int l, int r) { // sum on interval [l, r] r ++; T lres = ID, rres = ID; // make sure non-commutative operations work for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) { if (l&1) lres = comb(lres,seg[l++]); if (r&1) rres = comb(seg[--r],rres); } return comb(lres,rres); } }; Seg<ll, 2048> seg; int main(){ fast_io(); int n; cin >> n; set<ll> nums; f0r(i, n){ int ai, bi; cin >> ai >> bi; bounds.eb(mp(ai, bi)); nums.insert(ai); nums.insert(bi); } auto it1 = nums.begin(); auto it2 = next(it1); while(it2!= nums.end()){ ll val1 = *it1; ll val2 = *it2; if(val2 - val1>1){ ranges.eb(mp(val1+1, val2-1)); } it1 = next(it1); it2 = next(it2); } for(auto x: nums) ranges.eb(mp(x, x)); sort(all(ranges)); f0r(i, n){ f0r(j, sz(ranges)){ if(bounds[i].f<= ranges[j].f && bounds[i].s>= ranges[j].s){ possible[i].eb(j); } } } f0r(i, n){ for(int j: possible[i]){ dp[i][j] = ((ranges[j].s - ranges[j].f+1)%MOD) * (1+(j == 0? 0:seg.query(0, j-1))); dp[i][j] %= MOD; ll ways = ranges[j].s - ranges[j].f + 1; ways = ways*(ways-1)/2; ways%= MOD; ll tot = ways*seg.query(j, j); tot %= MOD; dp[i][j] += tot; dp[i][j] %= MOD; } for(int j: possible[i]){ seg.upd(j, seg.query(j, j) + dp[i][j]); } } cout << seg.query(0, sz(ranges) - 1) << endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
boat.cpp: In function 'void io(std::__cxx11::string)':
boat.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FIN, "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~
boat.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FOUT, "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...