Submission #277041

#	Time	Username	Problem	Language	Result	Execution time	Memory
277041		Masterdan	Meetings (IOI18_meetings)	C++14	36 / 100	1201 ms	432048 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define MAX 1e9+7
#define SMAX 1e18+7
#define all(a)  a.begin (), a.end ()
#define F  first
#define S  second
#define MIN -1
#define pb  push_back
#define mk  make_pair
#define mem(a, c)  memset(a, c, sizeof a)
#define pp pop_back
using namespace std;
typedef long long int ll;
typedef vector <int> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector <ll> vll;
ll mt[5010][5010];
int n, q;
const int N=1e5+10;
vector<pair<ii, ii> > tree;
pair<ii, ii> op(pair<ii, ii> a, pair<ii, ii> b){
    pair<ii, ii > ans;
    ans.F.S=a.F.S+b.F.S;
    ans.F.F=max(a.F.F, max(b.F.F, a.S.S+b.S.F));
    if(b.S.S==b.F.S)ans.S.S=a.S.S+b.S.S;
    else ans.S.S=b.S.S;
    if(a.S.F==a.F.S)ans.S.F=a.S.F+b.S.F;
    else ans.S.F=a.S.F;
    return ans;

}
void upd(int node, int in ,int fin, int pos, int val){
    if(pos>fin || pos<in)return;
    if(in==fin){
        tree[node].F.S=1;
        tree[node].F.F=val;
        tree[node].S.F=val;
        tree[node].S.S=val;
        return;
    }
    int mid=(in+fin)/2;
    upd(2*node+1, in, mid, pos, val);
    upd(2*node+2, mid+1, fin, pos, val);
    tree[node]=op(tree[2*node+1], tree[2*node+2]);
}
pair<ii, ii> vacio;
pair<ii, ii> query(int node, int in, int fin, int l, int r){
    if(in>r || fin<l)return vacio;
    if(in>=l && fin<=r )return tree[node];
    int mid=(in+fin)/2;
    return op(query(2*node+1, in, mid, l, r), query(2*node+2, mid+1, fin, l, r));
}
vector<long long> minimum_costs(vector<int> H,vector<int> l,vector<int> r) {
  vacio=mk(mk(0, 0), mk(0, 0));
  vll v;
  vll total;
  n=H.size ();
  q=l.size ();
  tree=vector<pair<ii, ii> > (N*4);
  for(int i=0;i<n;i++)v.pb(H[i]);
  int sw=0;
  for(int i=0;i<n;i++){
    if(v[i]>2)sw=1;
  }
  if(!sw){

    for(int i=0;i<n;i++){
        if(v[i]==2)upd(0, 0, n-1, i, 0);
        else upd(0, 0, n-1, i, 1);
    }
   // for(int i=0;i<=30;i++)cout<<tree[i].F.F<<" ";
   // cout<<endl;
    for(int i=0;i<q;i++){
        pair<ii, ii> ans=query(0, 0,n-1, l[i], r[i]);
        ll ans1=(r[i]-l[i]+1)*2;
        ans1-=ans.F.F;
        total.pb(ans1);
    }
    return total;
  }
  mem(mt, 0);
  //if(sw){
    for(int i=0;i<n;i++){
        ll maxi=v[i];
        mt[i][i]=v[i];
        for(int j=i-1;j>=0;j--){
            maxi=max(maxi, v[j]);
            mt[i][j]+=maxi+mt[i][j+1];
        }
        maxi=max(v[i], v[i+1]);
        mt[i][i+1]=maxi;
        for(int j=i+2;j<n;j++){
            maxi=max(maxi, v[j]);
            mt[i][j]+=maxi+mt[i][j-1];
        }
    }
    /*for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)cout<<mt[i][j]<<" ";
        cout<<endl;
    }*/
    for(int i=0;i<q;i++){
        ll ans=SMAX;
        for(int j=0;j<n;j++){
            if(r[i]==j)ans=min(ans, mt[j][l[i]]);
            else
            ans=min(ans, mt[j][l[i]]+mt[j][r[i]]);
        }
        total.pb(ans);
    }
    return total;
 // }
}
/*
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;
}


*/

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