Submission #1083310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083310		underwaterkillerwhale	Holiday (IOI14_holiday)	C++17	47 / 100	246 ms	10700 KiB

holiday

//#include"holiday.h"
 
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()
 
using namespace std;
 
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
 
const int N = 1e5 + 7;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const ll BASE = 137;
const int szBL = 350;
 
struct Segment_Tree {
    int m;
    pair<int, ll> st[N << 2];
 
    void init (int n) {
       m = n;
       rep (i, 1, n << 2) st[i].fs = st[i].se = 0;
    }
 
    pair<int, ll> mer (pair<int, ll> lc, pair<int, ll> rc) {
        pair<int, ll> cur;
        cur.fs = lc.fs + rc.fs;
        cur.se = lc.se + rc.se;
        return cur;
    }
 
    void update (int id, int l, int r, int pos, ll val) {
        if (l > pos || r < pos) return;
        if (l == r) {
            st[id].se += val;
            if (val < 0) --st[id].fs;
            else ++st[id].fs;
            return;
        }
        int mid = l + r >> 1;
        update (id << 1, l, mid, pos, val);
        update (id << 1 | 1, mid + 1, r, pos, val);
        st[id] = mer(st[id << 1], st[id << 1 | 1]);
    }
 
    ll walk (int id, int l, int r, int delta) {
        if (st[id].fs <= delta) return st[id].se;
        if (l == r) return 0;
        int mid = l + r >> 1;
        ll res = walk (id << 1 | 1, mid + 1, r, delta);
        if (st[id << 1 | 1].fs <= delta) {
            res += walk (id << 1, l, mid, delta - st[id << 1 | 1].fs);
        }
        return res;
    }
 
    void update (int pos, ll val) {
        if (val == 0) return;
        update (1, 1, m, pos, val);
    }
 
    ll walk (int delta) {
        return walk(1, 1, m, delta);
    }
}ST;
 
int cL = 1, cR = 0;
int n, St, D;
pii a[N];
ll dp[N];
int opt[N];
vector<pii> vec;
 
void go (int L, int R) {
    assert(L <= R);
    while (cL < L) {
        ST.update (a[cL].se, -a[cL].fs);
        ++cL;
    }
    while (cL > L) {
        --cL;
        ST.update (a[cL].se, a[cL].fs);
    }
    while (cR < R) {
        ++cR;
        ST.update (a[cR].se, a[cR].fs);
    }
    while (cR > R) {
        ST.update (a[cR].se, -a[cR].fs);
        --cR;
    }
}
 
void dnc (int L, int R, int optL, int optR) {
    if (L > R) return;
    int mid = L + R >> 1;
    ll best = -1;
    rep (i, optL, optR) {
        if(mid < i) go (mid, i);
        else go (i, mid);
        int delta = abs((mid - St) * 2 + St - i);
        ll curcost = ST.walk(D - delta);
        if (curcost >= best) { ///loz ma
            best = curcost;
            opt[mid] = i;
        }
    }
    dp[mid] = best;
    dnc(L, mid - 1, optL, opt[mid]);
    dnc(mid + 1, R, opt[mid], optR);
}
 
ll findMaxAttraction (int _n, int _St, int _D, int _a[]) {
 
//void solution () {
//    cin >> n >> St >> D;
    n = _n;
    St = _St;
    D = _D;
    ++St;
    rep (i, 1, n) {
//        cin >> a[i].fs;
        a[i].fs = _a[i - 1];
        vec.pb(MP(a[i].fs, i));
    }
    sort (ALL(vec));
    rep (i, 1, n) {
        a[i].se = lower_bound(ALL(vec), MP(a[i].fs, i)) - vec.begin() + 1;
    }
 
    ST.init(n), cL = 1, cR = 0;
    dnc (St + 1, n, 1, St);
    memset(opt, 0, sizeof opt);
    ST.init(n), cL = 1, cR = 0;
    dnc (1, St - 1, St, n);
 
    ST.init(n), cL = 1, cR = 0;
    rep (i, St, n) {
        go (St, i);
        int delta = i - St;
        ll curcost = ST.walk(D - delta);
        dp[i] = max(dp[i], curcost);
    }
 
    ST.init(n), cL = 1, cR = 0;
    rep (i, 1, St) {
        go (i, St);
        int delta = St - i;
        ll curcost = ST.walk(D - delta);
        dp[i] = max(dp[i], curcost);
    }
    return *max_element(dp + 1, dp + 1 + n);
//    cout << *max_element(dp + 1, dp + 1 + n) <<"\n";
}
 
//#define file(name) freopen(name".inp","r",stdin); \
//freopen(name".out","w",stdout);
//int main () {
//    file("c");
//    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int num_Test = 1;
////    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}
/*
no bug challenge +4
mình có muốn dùng mảng này không?
100 0 150
4 82 9 38 25 3 48 61 2 39 42 73 64 23 58 42 39 32 34 90 45 12 75 98 90 36 62 97 86 89 69 56 70 44 94 95 47 7 22 16 46 64 89 77 53 46 18 92 45 18 48 56 30 89 20 86 24 48 83 76 36 17 31 72 62 91 32 75 98 54 91 10 85 80 87 37 92 71 96 2 89 9 59 86 98 79 71 21 26 19 63 28 37 94 100 65 50 31 39 13
 
*/

Compilation message (stderr)

holiday.cpp:169:1: warning: multi-line comment [-Wcomment]
  169 | //#define file(name) freopen(name".inp","r",stdin); \
      | ^
holiday.cpp: In member function 'void Segment_Tree::update(int, int, int, int, long long int)':
holiday.cpp:53:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         int mid = l + r >> 1;
      |                   ~~^~~
holiday.cpp: In member function 'long long int Segment_Tree::walk(int, int, int, int)':
holiday.cpp:62:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int mid = l + r >> 1;
      |                   ~~^~~
holiday.cpp: In function 'void dnc(int, int, int, int)':
holiday.cpp:109:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |     int mid = L + R >> 1;
      |               ~~^~~

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