제출 #126380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
126380		nvmdava	휴가 (IOI14_holiday)	C++17	100 / 100	1151 ms	16452 KiB

holiday

#include "holiday.h"
#define ff first
#define ss second
#define ll long long
#include <bits/stdc++.h>
using namespace std;

long long res[2][2][250005];
int s, n;
int act[300005];
ll sum[300005];
int oid[100005];
ll a[100005];
vector<pair<int, int> > v;

void update(int id, int l, int r, int loc, int mul){
   act[id] += mul;
   sum[id] += a[loc] * mul;
   if(l == r) return;

   int m = (l + r) >> 1;
   if(m < loc) update(id << 1 | 1, m + 1, r, loc, mul);
   else update(id << 1, l, m, loc, mul);
}

int cl, cr;

ll query(int id, int l, int r, int k){
   if(k <= 0) return 0;
   if(act[id] <= k) return sum[id];
   int m = (l + r) >> 1;
   return query(id << 1, l, m, k) + query(id << 1 | 1, m + 1, r, k - act[id << 1]);
}

void push(int l, int r){
   if(r < l) swap(r, --l);
   while(l < cl)
      update(1, 1, n, oid[--cl], 1);
   while(cr < r)
      update(1, 1, n, oid[++cr], 1);
   while(cl < l)
      update(1, 1, n, oid[cl++], -1);
   while(cr > r)
      update(1, 1, n, oid[cr--], -1);
}

int c, d;
long long t = 0;
int find(int loc, int optl, int optr, int st){
   t = -1;
   int opt;
   int dx = 1;
   if(st == 0) swap(optl, optr), dx *= -1;
   optr += dx;
   for(int i = optl; i != optr; i += dx){
      push(s, i);
      long long w = query(1, 1, n, max(0, loc - c * abs(i - s)));
      if(w > t){
         t = w;
         opt = i;
      }
   }
   return opt;
}

void solve(int L, int R, long long f[]){
   queue<pair<pair<int, int>, pair<int, int> > > q;
   q.push({{0, d}, {L, R}});
   while(!q.empty()){
      int l = q.front().ff.ff, r = q.front().ff.ss, optl = q.front().ss.ff, optr = q.front().ss.ss;
      q.pop();
      int m = (l + r) >> 1;
      int opt = find(m, optl, optr, L == s);
      f[m] = max(t, 0ll);
      if(L == s){
         if(m > l)q.push({{l, m - 1}, {optl, opt}});
         if(m < r)q.push({{m + 1, r}, {opt, optr}});
      } else {
         if(m > l)q.push({{l, m - 1}, {opt, optr}});
         if(m < r)q.push({{m + 1, r}, {optl, opt}});
      }
   }
}

long long findMaxAttraction(int n, int start, int d, int a[]) {
   cl = cr = s = start + 1;
   ::n = n; ::d = d;
   for(int i = 0; i < n; i++)
      v.push_back({a[i], i + 1});
   sort(v.rbegin(), v.rend());
   for(int i = 0; i < n; i++){
      oid[v[i].ss] = i + 1;
      ::a[i + 1] = v[i].ff;
   }
   update(1, 1, n, oid[s], 1);
   c = 1;
   solve(1, s - 1, res[0][0]);
   solve(s, n, res[1][0]);
   c = 2;
   solve(1, s - 1, res[0][1]);
   solve(s, n, res[1][1]);
   long long ans = 0;
   for(int i = 0; i <= d; i++){
      ans = max(ans, max(res[0][1][i] + res[1][0][d - i], res[1][1][i] + res[0][0][d - i]));
   }
   return ans;
}

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

holiday.cpp: In function 'int find(int, int, int, int)':
holiday.cpp:63:11: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
    return opt;
           ^~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53