oj.uz

Submission #835740

# Submission time Handle Problem Language Result Execution time Memory
835740 2023-08-23T19:00:25 Z YassirSalama Meetings (IOI18_meetings) C++17
19 / 100
 465 ms 201036 KB 
#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
ll 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;
    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

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 60 ms 83276 KB Output is correct
3 Correct 62 ms 83276 KB Output is correct
4 Correct 63 ms 83272 KB Output is correct
5 Correct 61 ms 83280 KB Output is correct
6 Correct 60 ms 83288 KB Output is correct
7 Correct 58 ms 83252 KB Output is correct
8 Correct 64 ms 83244 KB Output is correct
9 Correct 61 ms 83276 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 60 ms 83276 KB Output is correct
3 Correct 62 ms 83276 KB Output is correct
4 Correct 63 ms 83272 KB Output is correct
5 Correct 61 ms 83280 KB Output is correct
6 Correct 60 ms 83288 KB Output is correct
7 Correct 58 ms 83252 KB Output is correct
8 Correct 64 ms 83244 KB Output is correct
9 Correct 61 ms 83276 KB Output is correct
10 Correct 300 ms 200860 KB Output is correct
11 Correct 465 ms 201008 KB Output is correct
12 Correct 307 ms 201036 KB Output is correct
13 Correct 465 ms 201036 KB Output is correct
14 Correct 320 ms 200972 KB Output is correct
15 Correct 302 ms 200964 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 13 ms 3924 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 13 ms 3924 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 60 ms 83276 KB Output is correct
3 Correct 62 ms 83276 KB Output is correct
4 Correct 63 ms 83272 KB Output is correct
5 Correct 61 ms 83280 KB Output is correct
6 Correct 60 ms 83288 KB Output is correct
7 Correct 58 ms 83252 KB Output is correct
8 Correct 64 ms 83244 KB Output is correct
9 Correct 61 ms 83276 KB Output is correct
10 Correct 300 ms 200860 KB Output is correct
11 Correct 465 ms 201008 KB Output is correct
12 Correct 307 ms 201036 KB Output is correct
13 Correct 465 ms 201036 KB Output is correct
14 Correct 320 ms 200972 KB Output is correct
15 Correct 302 ms 200964 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Runtime error 13 ms 3924 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -