Submission #390288

#	Time	Username	Problem	Language	Result	Execution time	Memory
390288		doowey	IOI Fever (JOI21_fever)	C++14	100 / 100	3308 ms	178176 KiB

fever

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 100;
ll H[N], W[N];
int dir[4][2] = {{0,+1},{0,-1},{+1,0},{-1,0}};
int n;

int sol = 0;

struct E{
    ll val;
    ll sec;
    int idx;
    bool operator<(const E &e) const {
        if(val == e.val)
            return sec < e.sec;
        return val < e.val;
    }
};

vector<E> vv[4][4];

struct node{
    pii low_val;
    pii sol;
    ll lazy;
};

struct segment_tree{
    vector<ll> vls;
    vector<node> pap;
    int m;
    void build(int node, int cl, int cr){
        pap[node].lazy = -(ll)1e18;
        if(cl == cr){
            pap[node].low_val = mp(vls[cl], cl);
            pap[node].sol = mp((ll)1e18, cl);
            return;
        }
        int mid = (cl + cr) / 2;
        build(node * 2, cl, mid);
        build(node * 2 + 1, mid + 1, cr);
        pap[node].low_val = min(pap[node*2].low_val, pap[node*2+1].low_val);
        pap[node].sol = min(pap[node*2].sol, pap[node*2+1].sol);
    }
    void init(vector<E> sha){
        vls.clear();
        pap.clear();
        m = sha.size();
        if(m == 0) return;
        pap.resize(4 * m + 16);
        for(int i = 0 ; i < m ; i ++ ){
            vls.push_back(sha[i].sec);
        }
        build(1, 0, m - 1);
    }
    void push(int node, int cl, int cr){
        pap[node].sol = min(pap[node].sol, mp(pap[node].low_val.fi - pap[node].lazy,pap[node].low_val.se));
        if(cl != cr){
            pap[node*2].lazy = max(pap[node*2].lazy, pap[node].lazy);
            pap[node*2+1].lazy = max(pap[node*2+1].lazy, pap[node].lazy);
        }
    }
    void update(int node, int cl, int cr, int tl, int tr, ll vv){
        push(node, cl, cr);
        if(cr < tl || cl > tr){
            return;
        }
        if(cl >= tl && cr <= tr){
            pap[node].lazy = max(pap[node].lazy, vv);
            push(node, cl, cr);
            return;
        }
        int mid = (cl + cr) / 2;
        update(node * 2, cl, mid, tl, tr, vv);
        update(node * 2 + 1, mid + 1, cr, tl, tr, vv);
        pap[node].sol = min(pap[node * 2].sol, pap[node * 2 + 1].sol);
    }
    void clean(int node, int cl, int cr, int id){
        push(node, cl, cr);
        if(cl == cr){
            pap[node].low_val = mp((ll)1e18, id);
            pap[node].sol = mp((ll)1e18, id);
            return;
        }
        int mid = (cl + cr) / 2;
        if(mid >= id)
            clean(node * 2, cl, mid, id);
        else
            clean(node * 2 + 1, mid + 1, cr, id);
        pap[node].low_val = min(pap[node*2].low_val, pap[node*2+1].low_val);
        pap[node].sol = min(pap[node * 2].sol, pap[node * 2 + 1].sol);
        pap[node].sol = min(pap[node].sol, mp(pap[node].low_val.fi - pap[node].lazy, pap[node].low_val.se));
    }
};

segment_tree opt[4][4];
int go[N];
ll low[N];

int solve(){
    go[0] = 0;
    for(int i = 2; i <= n; i ++ ){
        if(abs(H[i]) == abs(W[i])){
            if(W[i] < 0) go[i] = 0;
            else {
                if(H[i] > 0)
                    go[i] = 3;
                else
                    go[i] = 2;
            }
        }
        else{
            if(abs(H[i]) > abs(W[i])){
                if(H[i] > 0)
                    go[i] = 3;
                else
                    go[i] = 2;
            }
            else{
                if(W[i] > 0){
                    go[i] = 1;
                }
                else{
                    go[i] = 0;
                }
            }
        }
        low[i]=(ll)1e18;
    }
    low[1]=0;
    for(int p = 0 ; p < 4; p ++ ){
        for(int q = 0; q < 4; q ++ ){
            vv[p][q].clear();
        }
    }
    E cur;
    ll AH, AW;
    for(int p = 0 ; p < 4; p ++ ){
        for(int i = 1; i <= n; i ++ ){
            if(go[i] != p){
                AH = dir[p][0] - dir[go[i]][0];
                AW = dir[p][1] - dir[go[i]][1];
                cur.val = AW * 1ll * H[i] - AH * 1ll * W[i];
                if(AH != 0) cur.sec = H[i] / AH;
                else cur.sec = W[i] / AW;
                cur.idx = i;
                vv[p][go[i]].push_back(cur);
            }
        }
    }
    for(int p = 0 ; p < 4; p ++ ){
        for(int q = 0; q < 4; q ++ ){
            sort(vv[p][q].begin(), vv[p][q].end());
            opt[p][q].init(vv[p][q]);
        }
    }
    int cnt = 0;
    int id = -1;
    ll nw;
    int cid;
    ll add;
    int lf, rf;
    int nex;
    int iq;
    while(1){
        if(cnt == 0){
            id = 1;
            low[id] = 0;
        }
        else{
            nw = (ll)2e18;
            cid = -1;
            for(int p = 0;  p < 4; p ++ ){
                for(int q = 0; q < 4; q ++ ){
                    if(p == q || opt[p][q].m == 0) continue;
                    if(opt[p][q].pap[1].sol.fi < nw){
                        nw = opt[p][q].pap[1].sol.fi;
                        cid = vv[p][q][opt[p][q].pap[1].sol.se].idx;
                    }
                }
            }
            if(nw > (ll)1e14) break;
            id = cid;
            low[id] = nw;
        }
        cnt ++ ;
        for(int p = 0 ; p < 4; p ++ ){
            if(p == go[id]) continue;
            AH = dir[p][0] - dir[go[id]][0];
            AW = dir[p][1] - dir[go[id]][1];
            cur.val = AW * H[id] - AH * W[id];
            if(AH != 0) cur.sec = H[id] / AH;
            else cur.sec = W[id] / AW;
            cur.idx = -1;
            iq = lower_bound(vv[p][go[id]].begin(), vv[p][go[id]].end(), cur) - vv[p][go[id]].begin();
            opt[p][go[id]].clean(1, 0, opt[p][go[id]].m - 1, iq);
        }
        for(int nx = 0; nx < 4; nx ++ ){
            if(nx == go[id] || vv[go[id]][nx].empty()) continue;
            AH = dir[go[id]][0] - dir[nx][0];
            AW = dir[go[id]][1] - dir[nx][1];
            cur.val = AW * H[id] - AH * W[id];
            cur.sec = low[id];
            if(AH != 0) add = H[id] / AH;
            else add = W[id] / AW;
            cur.sec += add;
            lf = lower_bound(vv[go[id]][nx].begin(), vv[go[id]][nx].end(), cur) - vv[go[id]][nx].begin();
            if(lf < vv[go[id]][nx].size() && vv[go[id]][nx][lf].val == cur.val){
                rf = lf;
                for(int lg = 17; lg >= 0 ; lg -- ){
                    nex = rf + (1 << lg);
                    if(nex < vv[go[id]][nx].size() && vv[go[id]][nx][nex].val == cur.val){
                        rf = nex;
                    }
                }
                opt[go[id]][nx].update(1, 0, opt[go[id]][nx].m - 1, lf, rf, add);
            }
        }
    }
    return cnt;
}

int main(){
    fastIO;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> H[i] >> W[i];
        H[i] *= 2ll;
        W[i] *= 2ll;
        if(i > 1){
            H[i] -= H[1];
            W[i] -= W[1];
        }
    }
    H[1] = 0;
    W[1] = 0;
    int sol = solve();
    for(int i = 1; i <= n; i ++ ){
        W[i] = -W[i];
    }

    sol = max(sol, solve());
    for(int i = 1; i <= n; i ++ ){
        swap(H[i], W[i]);
    }
    sol = max(sol, solve());
    for(int i = 1; i <= n; i ++ ){
        W[i] = -W[i];
    }
    sol = max(sol, solve());
    cout << sol << "\n";
    return 0;
}

Compilation message (stderr)

fever.cpp: In function 'int solve()':
fever.cpp:220:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<E>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  220 |             if(lf < vv[go[id]][nx].size() && vv[go[id]][nx][lf].val == cur.val){
      |                ~~~^~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:224:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<E>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |                     if(nex < vv[go[id]][nx].size() && vv[go[id]][nx][nex].val == cur.val){
      |                        ~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32
• Subtask 7: 31 / 31