Submission #425631

#	Time	Username	Problem	Language	Result	Execution time	Memory
425631		MarcoMeijer	Meetings (IOI18_meetings)	C++14	19 / 100	5545 ms	6872 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<ii> vii;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()

vll minimum_costs(vi H, vi L, vi R) {
  int n = H.size();
  int q = L.size();
  vll C(q,0);
  RE(cq,q) {
    int l=L[cq], r=R[cq];
    vll sm; sm.assign(r-l+1,0);

    ll res = 0;
    vi stck;
    REP(i,l,r+1) {
      while(!stck.empty() && H[stck.back()] <= H[i]) {
        int x = stck.back();
        stck.pop_back();
        int j = stck.empty() ? l : stck.back() + 1;
        res += ll(x+1-j)*ll(H[i]-H[x]);
      }
      res += H[i];
      stck.pb(i);
      sm[i-l] += res;
    }

    res = 0;
    stck.clear();
    REV(i,l,r+1) {
      while(!stck.empty() && H[stck.back()] <= H[i]) {
        int x = stck.back();
        stck.pop_back();
        int j = stck.empty() ? r : stck.back() - 1;
        res += ll(j+1-x)*ll(H[i]-H[x]);
      }
      res += H[i];
      stck.pb(i);
      sm[i-l] += res;
    }

    REP(i,l,r+1) sm[i-l] -= H[i];
    C[cq] = sm[0];
    FOR(i,sm) C[cq] = min(C[cq],i);
  }
  return C;
}

Compilation message (stderr)

meetings.cpp: In function 'vll minimum_costs(vi, vi, vi)':
meetings.cpp:22:7: warning: unused variable 'n' [-Wunused-variable]
   22 |   int n = H.size();
      |       ^

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