Submission #835729

#	Time	Username	Problem	Language	Result	Execution time	Memory
835729		YassirSalama	Meetings (IOI18_meetings)	C++17	0 / 100	5569 ms	1996 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
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;
ll tree[4*MAXN];
int n;
vector<ll> v;
void build(int node,int l,int r){
    if(l==r){
        tree[node]=v[l];
        return;
    }
    int mid=(l+r)/2;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    tree[node]=max(tree[node<<1],tree[node<<1|1]);
}
ll query(int node,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return tree[node];
    int mid=(l+r)/2;
    ll ans=0;
    if(ql<=mid) ans=max(ans,query(node<<1,l,mid,ql,qr));
    if(qr>mid) ans=max(ans,query(node<<1|1,mid+1,r,ql,qr));
    return ans;
}
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(1,0,n-1);
    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(1,0,n-1,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: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40