oj.uz

Submission #713913

# Submission time Handle Problem Language Result Execution time Memory
713913 2023-03-23T08:14:18 Z alvingogo Meetings (IOI18_meetings) C++14
17 / 100
 45 ms 15208 KB 
#include <bits/stdc++.h>
#include "meetings.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct ST{
    vector<vector<int> > dp;
    void init(vector<int> x){
        int n=x.size();
        dp.resize(20,vector<int>(n));
        dp[0]=x;
        for(int i=1;i<20;i++){
            for(int j=0;j+(1<<(i-1))<n;j++){
                dp[i][j]=max(dp[i-1][j],dp[i-1][j+(1<<(i-1))]);
            }
        }
    }
    int query(int l,int r){
        if(l>r){
            return 0;
        }
        int x=__lg(r-l+1);
        return max(dp[x][l],dp[x][r-(1<<x)+1]);
    }

}szt;
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
    int n=h.size(),q=l.size();
    vector<long long> ans(q);
    vector<int> a(n,-1),b(n,-1);
    int c=-1;
    for(int i=0;i<n;i++){
        if(h[i]==1){
            if(c==-1){
                c=i;
            }
            a[i]=c;
        }
        else{
            c=-1;
        }
    }
    c=n;
    for(int i=n-1;i>=0;i--){
        if(h[i]==1){
            if(c==-1){
                c=i;
            }
            b[i]=c;
        }
        else{
            c=-1;
        }
    }
    vector<int> gg(n);
    for(int j=0;j<n;j++){
        if(h[j]==2){
            continue;
        }
        gg[j]=b[j]-a[j]+1;
    }
    szt.init(gg);
    for(int i=0;i<q;i++){
        int x=0;
        int u=l[i],v=r[i];
        if(h[l[i]]==1){
            x=max(x,b[l[i]]-l[i]+1);
            u=b[l[i]]+1;
        }
        if(h[r[i]]==1){
            x=max(x,r[i]-a[r[i]]+1);
            v=a[r[i]]-1;
        }
        x=max(x,szt.query(u,v));
        x=min(x,r[i]-l[i]+1);
        ans[i]=2*(r[i]-l[i]+1)-x;
    }
    return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 15 ms 2384 KB Output is correct
3 Correct 45 ms 15208 KB Output is correct
4 Correct 43 ms 15144 KB Output is correct
5 Correct 44 ms 15152 KB Output is correct
6 Correct 45 ms 15156 KB Output is correct
7 Correct 42 ms 15184 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 15 ms 2384 KB Output is correct
3 Correct 45 ms 15208 KB Output is correct
4 Correct 43 ms 15144 KB Output is correct
5 Correct 44 ms 15152 KB Output is correct
6 Correct 45 ms 15156 KB Output is correct
7 Correct 42 ms 15184 KB Output is correct
8 Incorrect 43 ms 15180 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -