제출 #586831

#제출 시각아이디문제언어결과실행 시간메모리
586831Red_Inside휴가 (IOI14_holiday)C++17
24 / 100
15 ms2516 KiB
#include "holiday.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define f first #define s second #define forn(j, i, n) for(int i = j; i <= n; ++i) #define FOR(j, i, n) for(int i = j; i < n; ++i) #define nfor(j, i, n) for(int i = n; i >= j; --i) #define IOS ios_base::sync_with_stdio(false), cin.tie(), cout.tie(); #define all(v) v.begin(), v.end() const int maxn = 7e3+100; //#define int ll #define pii pair <int, int> ll inf = 1e18; ll n, m, ukl, ukr, d, ts[4*maxn], tc[4*maxn], pos[maxn], a[maxn], res = -inf; pair <ll, int> b[maxn]; void upd(int v, int tl, int tr, int pos, ll val) { // if(v == 1) cout << "UPDATE " << pos << " " << val << endl; if(pos < tl || tr < pos) return; if(tl == tr) { ts[v] += val; if(ts[v] > 0) tc[v]++; else tc[v]--; return; } upd(v * 2, tl, (tl + tr) / 2, pos, val); upd(v * 2 + 1, (tl + tr) / 2 + 1, tr, pos, val); ts[v] = ts[v * 2] + ts[v * 2 + 1]; tc[v] = tc[v * 2] + tc[v * 2 + 1]; } ll get(int v, int tl, int tr, int k) { if(tl == tr) { return ts[v]; } if(tc[v * 2 + 1] >= k) return get(v * 2 + 1, (tl + tr) / 2 + 1, tr, k); else return get(v * 2, tl, (tl + tr) / 2, k - tc[v * 2 + 1]) + ts[v * 2 + 1]; } void print(int v, int tl, int tr) { if(tl == tr) { cout << tl << " " << tr << " " << ts[v] << " " << tc[v] << endl; return; } print(v * 2, tl, (tl + tr) / 2); cout << tl << " " << tr << " " << ts[v] << " " << tc[v] << endl; print(v * 2 + 1, (tl + tr) / 2 + 1, tr); } void solve(int l, int r, int optl = m, int optr = n) { if(l > r) return; int mid = (l + r) / 2; while(ukl > mid) { ukl--; upd(1, 1, n, pos[ukl], a[ukl]); } while(ukl < mid) { upd(1, 1, n, pos[ukl], -a[ukl]); ukl++; } ll ans = -inf; int opt; forn(optl, i, optr) { while(ukr < i) { ukr++; upd(1, 1, n, pos[ukr], a[ukr]); } while(ukr > i) { upd(1, 1, n, pos[ukr], -a[ukr]); ukr--; } //m-mid //i-m // cout << "FOR " << mid << " " << i << " " << d-(i-mid+min(i-m, m-mid)) << " " << get(1, 1, n, d-(i-mid+min(i-m, m-mid))) << " " << ukl << " " << ukr << endl; // print(1, 1, n); ll temp = get(1, 1, n, d-(i-mid+min(i-m, m-mid))); res = max(res, temp); if(temp > ans) { ans = temp; opt = i; } } // cout << mid << " " << opt << endl; solve(l, mid-1, optl, opt); solve(mid+1, r, opt, optr); } long long int findMaxAttraction(int N, int start, int D, int attraction[]) { n = N; d = D; forn(1, i, n) { b[i].f = attraction[i-1]; b[i].s = i; a[i] = b[i].f; } sort(b + 1, b + 1 + n); forn(1, i, n) { pos[b[i].s] = i; } start++; m = start; ukr = start; ukl = start; upd(1, 1, n, pos[start], a[start]); solve(1, start); return res; }

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

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:102:7: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |  solve(l, mid-1, optl, opt);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...