Submission #995564

#	Time	Username	Problem	Language	Result	Execution time	Memory
995564		Muhammet	Closing Time (IOI23_closing)	C++17	0 / 100	1002 ms	64860 KiB

closing

#include <bits/stdc++.h>

#define ll long long
#define N 30005
#define sz(s) (int)s.size()
#define ff first
#define ss second

using namespace std;

map <pair<int,int>, int> m;

ll lz[N], st[N];

void upd(int nd, int l, int r, int a, int b, int vl){
    if((r < a) or (l > b)) return;
    if(l >= a and r <= b) {
        lz[nd] += ((r-l+1) * vl);
        return;
    }
    int md = (r-l)/2;
    upd(nd*2,l,md,a,b,vl);
    upd(nd*2+1,md+1,r,a,b,vl);
}

ll fnd(int nd, int l, int r, int ind){
    st[nd] += lz[nd];
    lz[nd] /= (r-l+1);
    int md = (r-l)/2;
    lz[nd*2] += (lz[nd]*(md-l+1));
    lz[nd*2+1] += (lz[nd]*(r-md));
    lz[nd] = 0;
    if(l > ind or r < ind) return 0;
    if(ind == l and r == ind) return st[nd];
    return fnd(nd*2,l,md,ind) + fnd(nd*2+1,md+1,r,ind);
}

int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> u1, vector<int> t){
    m.clear();
    for(int i = 0; i < 20005; i++) lz[i] = st[i] = 0;
    for(int i = 0; i < sz(u); i++){
        m[{u[i],u1[i]}] = t[i];
        m[{u1[i],u[i]}] = t[i];
    }
    if(x > y) swap(x,y);
    ll l1 = x, r1 = x, l2 = y, r2 = y, ans = 0;
    while(1){
        ll mn = 1e15, z = 0, z1 = -1, z2 = -1;
        if(l1 > 0){
            z = m[{l1,l1-1}];
            z -= fnd(1,0,n-1,l1);
            z = max(z,0ll);
            if(z <= mn){
                mn = z;
                z1 = l1;
                z2 = x;
            }
        }
        if(r1 < n-1){
            z = m[{r1,r1+1}];
            z -= fnd(1,0,n-1,r1);
            z = max(z,0ll);
            if(z <= mn){
                mn = z;
                z1 = r1;
                z2 = x;
            }
        }
        if(l2 > 0){
            z = m[{l2,l2-1}];
            z -= fnd(1,0,n-1,l2);
            z = max(z,0ll);
            if(z <= mn){
                mn = z;
                z1 = l2;
                z2 = y;
            }
        }
        if(r2 < n-1){
            z = m[{r2,r2+1}];
            z -= fnd(1,0,n-1,r2);
            z = max(z,0ll);
            if(z <= mn){
                mn = z;
                z1 = r2;
                z2 = x;
            }
        }
        if(mn > k or z1 == -1) break;
        k -= mn;
        ans++;
        upd(1,0,n-1,min(z1,z2),max(z1,z2),mn);
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17