oj.uz

Submission #995564

# Submission time Handle Problem Language Result Execution time Memory
995564 2024-06-09T11:20:01 Z Muhammet Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 64860 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 197 ms 64860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1002 ms 600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1002 ms 600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1002 ms 600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -