Submission #285420

#	Time	Username	Problem	Language	Result	Execution time	Memory
285420		peti1234	Meetings (IOI18_meetings)	C++17	19 / 100	910 ms	392312 KiB

meetings

#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) {
    if (n<=5000 && q<=5000) {
        n=h.size(), q=l.size();
        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]=jobb[i]-bal[i]+1;
    for (int j=1; j<18; j++) {
        for (int i=0; i<n; i++) {
            int p=max(n-1, i+(1<<(j-1)));
            ert[i][j]=max(ert[i][j-1], ert[p][j-1]);
        }
    }
    for (int i=0; i<n; 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(k-p);
    }
    return sz;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40