Submission #835733

#	Time	Username	Problem	Language	Result	Execution time	Memory
835733		YassirSalama	Meetings (IOI18_meetings)	C++17	4 / 100	5593 ms	3168 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define ll long long
#define OVL(v,s) for(auto x:v) cout<<x<<s;cout<<endl;
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define mod 1000000007
const ll INF=1e18;
const int MAXN=1e5;
const int LOGN=18;
ll lg[MAXN];
vector<ll> v;
int n;
ll st[MAXN][LOGN];
void build(){
    for(int i=0;i<n;i++) st[i][0]=v[i];
    for(int j=1;j<LOGN;j++){
        for(int i=0;i+(1<<j)<=n;i++){
            st[i][j]=max(
                    st[i][j-1],
                    st[i+(1<<(j-1))][j-1]
                );
        }
    }
    lg[1]=0;
    for(int i=2;i<MAXN;i++){
        lg[i]=lg[i/2]+1;
    }
}
int query(int l,int r){
    int k=r-l+1;
    k=lg[k];
    return max(
            st[l][k],
            st[r-(1<<k)+1][k]
        );
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
    n=H.size();
    for(auto x:H){
        v.push_back(x);
    }
    int q=L.size();
    vector<ll> anss;
    build();
    for(int qu=0;qu<q;qu++){
        int l=L[qu];
        int r=R[qu];
        ll BIGANS=INF;
        for(int x=l;x<=r;x++){
            ll ans=0;
            for(int i=l;i<=r;i++){
                // dbg(x,i,query(1,0,n-1,min(i,x),max(i,x)));
                ans+=query(min(i,x),max(i,x));
            }
            // dbg(x,ans);
            BIGANS=min(ans,BIGANS);
        }
        anss.push_back(BIGANS);
    }
    return anss;
}



#ifdef IOI
#include <cstdio>
#include <cstdlib>
#include <vector>
#include "meetings.h"

namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int N = read_int();
  int Q = read_int();
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    H[i] = read_int();
  }
  std::vector<int> L(Q), R(Q);
  for (int j = 0; j < Q; ++j) {
    L[j] = read_int();
    R[j] = read_int();
  }

  std::vector<long long> C = minimum_costs(H, L, R);
  for (size_t j = 0; j < C.size(); ++j) {
    printf("%lld\n", C[j]);
  }
  return 0;
}

#endif

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