oj.uz

Submission #232110

# Submission time Handle Problem Language Result Execution time Memory
232110 2020-05-16T04:43:35 Z anonymous Holiday (IOI14_holiday) C++14
100 / 100
 4396 ms 10968 KB 
#include"holiday.h"
#include <map>
#include <vector>
#include <algorithm>
#include <cassert>
#define LL long long
#define MAXN 100005
using namespace std;
LL ans;
int A[MAXN], D, S, N;
map <int,int> Lookup;
vector <int> Sweep;
int Val[MAXN], pt;

class DS {
    LL ST[MAXN * 4][2];
    void pushup(int cur) {
        ST[cur][0] = ST[2*cur][0] + ST[2*cur+1][0];
        ST[cur][1] = ST[2*cur][1] + ST[2*cur+1][1];
    }
public:
    void nuke(int l, int r, int cur) {
        ST[cur][0] = ST[cur][1] = 0;
        if (l != r) {
            int mid = (l + r) >> 1;
            nuke(l, mid, 2*cur);
            nuke(mid+1, r, 2*cur+1);
        }
    }
    void upd(bool b, int ind, int l, int r, int cur) {
        if (ind < l || ind > r) {return;}
        if (l == r) {
            ST[cur][1] += b ? 1 : -1;
            ST[cur][0] += b ? Val[l] : -Val[l];
        } else {
            int mid = (l + r) >> 1;
            upd(b, ind, l, mid, 2*cur);
            upd(b, ind, mid+1, r, 2*cur+1);
            pushup(cur);
        }
    }
    LL kth(int k, int l, int r, int cur) {
        if (l == r) {
            return(((LL) Val[l])*(min((LL) k, ST[cur][1])));
        } else {
            int mid = (l + r) >> 1;
            if (ST[2*cur+1][1] < k) { //early exit?
                return(ST[2*cur+1][0] +
                       kth(k - ST[2*cur+1][1], l, mid, 2*cur));
            } else {
                return(kth(k, mid+1, r, 2*cur+1));
            }
        }
    }
    void add(int v) {
        if (v == 0) {return;}
        upd(1, Lookup[v], 0, pt, 1);
    }
    void del(int v) {
        if (v == 0) {return;}
        upd(0, Lookup[v], 0, pt, 1);
    }
    LL ask(int x) {
        if (x < 0) {return(-1LL<<60);}
        return(kth(x, 0, pt, 1));
    }

} KQ;

void Compress() {
     for (int i=0; i<N; i++) {
        Sweep.push_back(A[i]);
     }
     sort(Sweep.begin(), Sweep.end());
     for (int i=0; i<N; i++) {
        if (i == 0 || Sweep[i] != Sweep[i-1]) {
            Val[pt] = Sweep[i];
            Lookup[Sweep[i]] = pt;
            pt++;
        }
     }
     pt--;
     assert((Sweep.size() == N) && (pt <= N));
}

void slv(int l, int r, int lo, int hi, int pl, int pr) {
    //printf("%d %d %d %d\n",l,r,lo,hi);
    if (l > r) {return;}
    int p = (l + r) >> 1;
    int pL = pl, pR = pr;
    while (pl > hi+1) {
        KQ.add(A[pl-1]);
        pl--;
    }
    while (pr < p) {
        KQ.add(A[pr+1]);
        pr++;
    }
    while (pl <hi+1) {
        KQ.del(A[pl]);
        pl++;
    }
    while (pr > p) {
        KQ.del(A[pr]);
        pr--;
    }

    LL opt=-1, optval=-1LL<<60;
    for (int i=hi; i>=lo; i--) {
        KQ.add(A[i]);
        LL res = KQ.ask(D-S + 2*i - p);
        if (res >= optval) {
            opt = i;
            optval = res;
            ans = max(ans, res);
        }
    }
    slv(l, p-1, lo, opt, lo, p);
    slv(p+1,r, opt, hi, lo, p);
    //reset pos
    while (lo < pL) {
        KQ.del(A[lo]);
        lo++;
    }
    while (lo > pL) {
        KQ.add(A[lo-1]);
        lo--;
    }
    while (p < pR) {
        KQ.add(A[p+1]);
        p++;
    }
    while (p > pR) {
        KQ.del(A[p]);
        p--;
    }
}

void slvL() {
    for (int i=S; i>=0; i--) { //one direction
        KQ.add(A[i]);
        ans  = max(ans, KQ.ask(D-S+i));
    }
    slv(S+1, N-1, 0, S-1, 0, S);
    KQ.nuke(0, pt, 1);
}

LL findMaxAttraction(int n, int s, int d, int a[]) { //len, start, days, val
    N = n, S = s, D = d;
    for (int i=0; i<n; i++) {A[i] = a[i];}
    Compress();
    slvL();
    for (int i=0; i<=n/2; i++) {
        swap(A[i], A[n-1-i]);
    }
    S = N -   1 - S;
    slvL();
    return(ans);
}

Compilation message

In file included from /usr/include/c++/7/cassert:44:0,
                 from holiday.cpp:5:
holiday.cpp: In function 'void Compress()':
holiday.cpp:83:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      assert((Sweep.size() == N) && (pt <= N));
              ~~~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1820 KB Output is correct
2 Correct 20 ms 1788 KB Output is correct
3 Correct 31 ms 1788 KB Output is correct
4 Correct 21 ms 1916 KB Output is correct
5 Correct 179 ms 1788 KB Output is correct
6 Correct 55 ms 896 KB Output is correct
7 Correct 98 ms 1280 KB Output is correct
8 Correct 119 ms 1280 KB Output is correct
9 Correct 39 ms 768 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 640 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 11 ms 640 KB Output is correct
4 Correct 32 ms 640 KB Output is correct
5 Correct 28 ms 640 KB Output is correct
6 Correct 10 ms 512 KB Output is correct
7 Correct 11 ms 384 KB Output is correct
8 Correct 12 ms 384 KB Output is correct
9 Correct 9 ms 384 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1788 KB Output is correct
2 Correct 400 ms 10724 KB Output is correct
3 Correct 1200 ms 5628 KB Output is correct
4 Correct 36 ms 640 KB Output is correct
5 Correct 12 ms 384 KB Output is correct
6 Correct 12 ms 384 KB Output is correct
7 Correct 9 ms 384 KB Output is correct
8 Correct 4396 ms 10968 KB Output is correct
9 Correct 4250 ms 10864 KB Output is correct