oj.uz

Submission #285431

# Submission time Handle Problem Language Result Execution time Memory
285431 2020-08-28T23:07:38 Z peti1234 Meetings (IOI18_meetings) C++17
36 / 100
 892 ms 392312 KB 
#include <bits/stdc++.h>

using namespace std;
const int c=5002, cc=100002;
vector<long long> sz;
int n, bal[cc], jobb[cc], ert[cc][20];

long long q, maxi[c][c], kom[c][c];
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
    n=h.size(), q=l.size();
    if (n<=5000 && q<=5000) {
        for (int i=0; i<n; i++) maxi[i][i]=h[i];
        for (int i=0; i<n; i++) for (int j=i+1; j<n; j++) maxi[i][j]=max(maxi[i][j-1], maxi[j][j]);
        for (int i=0; i<n; i++) for (int j=0; j<i; j++) maxi[i][j]=maxi[j][i];
        for (int i=0; i<n; i++) for (int j=1; j<=n; j++) kom[i][j]=kom[i][j-1]+maxi[i][j-1];
        for (int i=0; i<q; i++) {
            long long ans=1e18;
            for (int j=l[i]; j<=r[i]; j++) {
                ans=min(ans, kom[j][r[i]+1]-kom[j][l[i]]);
            }
            sz.push_back(ans);
        }
        return sz;
    }
    for (int i=0; i<n; i++) {
        if (h[i]==2) {
            for (int j=i-1; j>=0 && h[j]==1; j--) jobb[j]=i;
            jobb[i]=i;
        }
    }
    for (int i=n-1; i>=0 && h[i]==1; i--) jobb[i]=n;
    for (int i=n-1; i>=0; i--) {
        if (h[i]==2) {
            for (int j=i+1; j<n && h[j]==1; j++) bal[j]=i;
            bal[i]=i;
        }
    }
    for (int i=0; i<n && h[i]==1; i++) bal[i]=-1;
    for (int i=0; i<n; i++) ert[i][0]=max(0, jobb[i]-bal[i]-1);
    for (int j=1; j<18; j++) {
        for (int i=0; i<n; i++) {
            int p=min(n-1, i+(1<<(j-1)));
            ert[i][j]=max(ert[i][j-1], ert[p][j-1]);
        }
    }
    for (int i=0; i<q; i++) {
        int a=l[i], b=r[i], k=b-a+1, p=0, po=1, db=0;
        if (bal[b]<a) p=k;
        else {
            p=max(jobb[a]-a, b-bal[b]), a=jobb[a], b=bal[b];
            while(2*po<=b-a) po*=2, db++;
            p=max({p, ert[a][db], ert[b-po+1][db]});
        }
        sz.push_back(2*k-p);
    }
    return sz;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 197 ms 165372 KB Output is correct
3 Correct 202 ms 165368 KB Output is correct
4 Correct 200 ms 165368 KB Output is correct
5 Correct 200 ms 165368 KB Output is correct
6 Correct 199 ms 165368 KB Output is correct
7 Correct 198 ms 165444 KB Output is correct
8 Correct 199 ms 165368 KB Output is correct
9 Correct 200 ms 165364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 197 ms 165372 KB Output is correct
3 Correct 202 ms 165368 KB Output is correct
4 Correct 200 ms 165368 KB Output is correct
5 Correct 200 ms 165368 KB Output is correct
6 Correct 199 ms 165368 KB Output is correct
7 Correct 198 ms 165444 KB Output is correct
8 Correct 199 ms 165368 KB Output is correct
9 Correct 200 ms 165364 KB Output is correct
10 Correct 746 ms 392184 KB Output is correct
11 Correct 892 ms 392264 KB Output is correct
12 Correct 744 ms 392212 KB Output is correct
13 Correct 890 ms 392132 KB Output is correct
14 Correct 754 ms 392312 KB Output is correct
15 Correct 751 ms 392312 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 24 ms 2808 KB Output is correct
3 Correct 100 ms 13036 KB Output is correct
4 Correct 74 ms 13036 KB Output is correct
5 Correct 78 ms 13036 KB Output is correct
6 Correct 76 ms 13036 KB Output is correct
7 Correct 80 ms 13036 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 24 ms 2808 KB Output is correct
3 Correct 100 ms 13036 KB Output is correct
4 Correct 74 ms 13036 KB Output is correct
5 Correct 78 ms 13036 KB Output is correct
6 Correct 76 ms 13036 KB Output is correct
7 Correct 80 ms 13036 KB Output is correct
8 Incorrect 73 ms 13008 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 197 ms 165372 KB Output is correct
3 Correct 202 ms 165368 KB Output is correct
4 Correct 200 ms 165368 KB Output is correct
5 Correct 200 ms 165368 KB Output is correct
6 Correct 199 ms 165368 KB Output is correct
7 Correct 198 ms 165444 KB Output is correct
8 Correct 199 ms 165368 KB Output is correct
9 Correct 200 ms 165364 KB Output is correct
10 Correct 746 ms 392184 KB Output is correct
11 Correct 892 ms 392264 KB Output is correct
12 Correct 744 ms 392212 KB Output is correct
13 Correct 890 ms 392132 KB Output is correct
14 Correct 754 ms 392312 KB Output is correct
15 Correct 751 ms 392312 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 24 ms 2808 KB Output is correct
18 Correct 100 ms 13036 KB Output is correct
19 Correct 74 ms 13036 KB Output is correct
20 Correct 78 ms 13036 KB Output is correct
21 Correct 76 ms 13036 KB Output is correct
22 Correct 80 ms 13036 KB Output is correct
23 Incorrect 73 ms 13008 KB Output isn't correct
24 Halted 0 ms 0 KB -