oj.uz

Submission #126380

# Submission time Handle Problem Language Result Execution time Memory
126380 2019-07-07T14:47:17 Z nvmdava Holiday (IOI14_holiday) C++17
100 / 100
 1151 ms 16452 KB 
#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;
}

Compilation message

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 372 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 13752 KB Output is correct
2 Correct 638 ms 13444 KB Output is correct
3 Correct 817 ms 13464 KB Output is correct
4 Correct 661 ms 13456 KB Output is correct
5 Correct 1151 ms 10988 KB Output is correct
6 Correct 348 ms 8740 KB Output is correct
7 Correct 599 ms 6616 KB Output is correct
8 Correct 692 ms 6788 KB Output is correct
9 Correct 276 ms 11012 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 888 KB Output is correct
2 Correct 17 ms 888 KB Output is correct
3 Correct 17 ms 888 KB Output is correct
4 Correct 20 ms 632 KB Output is correct
5 Correct 18 ms 632 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 6 ms 504 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 797 ms 16388 KB Output is correct
2 Correct 1031 ms 16452 KB Output is correct
3 Correct 350 ms 3824 KB Output is correct
4 Correct 16 ms 632 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 1144 ms 8488 KB Output is correct
9 Correct 1110 ms 8504 KB Output is correct