Submission #123665

#	Time	Username	Problem	Language	Result	Execution time	Memory
123665		Masterdan	Meetings (IOI18_meetings)	C++14	19 / 100	733 ms	196660 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define MIN -1
#define MAX 1000000000000000000
#define pb push_back
#define mp  make_pair
#define F first
#define S second
#define all(a)   a.begin (), a.end ()
typedef long long int ll;
ll m[5010][5010];
ll tree[400100][4];
ll v[100100];
vector <ll> v1;
void init(int  node, int a, int  b){
    if(a==b){
        if(v[a]==2){
            tree[node][0]=0;
            tree[node][1]=0;
            tree[node][2]=0;
        }else {
            tree[node][0]=1;
            tree[node][1]=1;
            tree[node][2]=1;
        }
        return ;
    }
    init(2*node+1, a, (a+b)/2);
    init(2*node+2, (a+b)/2+1, b);
    if(tree[2*node+1][0]>=1){
        tree[node][0]=tree[2*node+1][0]+tree[2*node+2][0];
    }else tree[node][0]=0;
    if(tree[2*node+2][2]>=1){
        tree[node][2]=tree[2*node+1][2]+tree[2*node+2][2];
    }else{
        tree[node][2]=0;
    }
    if(tree[2*node+1][2]>=1 and tree[2*node+2][0]>=1){
        tree[node][1]=tree[2*node+1][1]+tree[2*node+2][1];
    }else tree[node][1]=max(tree[2*node+1][1], tree[2*node+2][1]);

}
int query(int node, int a, int b, int p, int q){
    if(q<a or b<p)return 0;
    if(p<=a and b<=q)return tree[node][1];
        if(tree[2*node+1][2]>=1 and tree[2*node+2][0]>=1){
            return query(2*node+1,a, (a+b)/2, p , q)+query(2*node+2,(a+b)/2+1,b,p, q);
        }else return max (query(2*node+1,a, (a+b)/2, p , q),query(2*node+2,(a+b)/2+1,b,p, q));
}
vector<ll> minimum_costs(vector<int> h, vector<int > l,vector<int > r) {
    int n=h.size ();
    //memset(m, 0, sizeof h.size ());
  int Q = l.size();
  vector<ll> C(Q);
  int sw=0;
  for(int i=0;i<n;i++){
    if(h[i]>2){
        sw=1;
        break;
    }
  }
      if(sw==1){
            memset(m, 0, sizeof h.size());
         for(int i=0;i<n;i++){
            int maxi=h[i];
        for(int j=i-1;j>=0;j--){
            m[i][j]+=max(maxi, h[j]);
            m[i][j]+=m[i][j+1];
            maxi=max(maxi, h[j]);
        }
        maxi=h[i];
        m[i][i]=h[i];
        for(int j=i+1;j<n;j++){
            m[i][j]+=max(h[j], maxi);
            m[i][j]+=m[i][j-1];
            maxi=max(h[j], maxi);
        }
      }
      for (int k = 0; k < Q; ++k) {
            ll mini=MAX;
            for(int i=l[k];i<=r[k];i++){
                if(i==l[k]){
                    mini=min(m[i][r[k]], mini);
                }else{
                    mini=min(m[i][r[k]]+m[i][l[k]], mini);
                }
            }
            C[k]=mini;
      }
      return C;
      }
  for(int i=0;i<n;i++){
    v[i]=h[i];
  }
  init(0, 0, n);
  for (int k = 0; k < Q; ++k) {
        ll s1=0;
        ll s=query(0, 0, n, l[k] , r[k]);
        v1.push_back(s);
        int t=r[k]+1-l[k];
        s1+=(t-s)*2;
        s1+=s;
        C[k]=s1;
  }
  return C;
}
/*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", v1[j]);
    printf("%lld\n", C[j]);
  }
  return 0;
}
*/

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