Submission #835737

#	Time	Username	Problem	Language	Result	Execution time	Memory
835737		YassirSalama	Meetings (IOI18_meetings)	C++17	0 / 100	47 ms	47964 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=5100;
const int LOGN=18;
ll lg[MAXN];
vector<ll> v;
int n;
ll st[MAXN][LOGN];
//sparse table
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]
        );
}
//dp preprocess
int dp[MAXN][MAXN];//dp[x][i] is the prefix sum from dp[x][0] to dp[x][i] if we used x
void build2(){
    for(int x=0;x<n;x++){
        for(int i=0;i<n;i++){
            dp[x][i]=query(min(i,x),max(i,x));
        }
        for(int i=1;i<n;i++)
            dp[x][i]+=dp[x][i-1];
    }
}
ll prefsum(int x,int l,int r){
    ll ans=0;
    ans=dp[x][r]-(l==0?0LL:dp[x][l-1]);
    return dp[x][r]-((l==0)?0LL:dp[x][l-1]);
}
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();
    build2();
    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++){
            BIGANS=min(BIGANS,prefsum(x,l,r));
        }
        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

Compilation message (stderr)

meetings.cpp: In function 'long long int prefsum(int, int, int)':
meetings.cpp:60:8: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   60 |     ll ans=0;
      |        ^~~

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