Submission #125187

#	Time	Username	Problem	Language	Result	Execution time	Memory
125187		Masterdan	Meetings (IOI18_meetings)	C++14	19 / 100	718 ms	196656 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];
int y;
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);
    tree[node][1]=max(tree[2*node+1][1],max(tree[2*node+2][1], tree[2*node+1][2]+tree[2*node+2][0]));
    if(abs(a-b)+1==tree[2*node+2][2])tree[node][2]=max(tree[2*node+2][2], tree[2*node+2][2]+tree[2*node+1][2]);
    else tree[node][2]=tree[2*node+2][2];
    if(abs(a-b)+1==tree[2*node+1][0])tree[node][0]=max(tree[2*node+1][0], tree[2*node+1][0]+tree[2*node+2][0]);
    else tree[node][0]=tree[2*node+1][0];
}
int query(int node, int a, int b, int p, int q, int pos){
    if(q<a or b<p)return -1;
    if(p<=a and b<=q)return tree[node][pos];
        if(pos==1){
            int ans1=query(2*node+1, a, (a+b)/2, p , q, 1);
            int ans2=query(2*node+2,(a+b)/2+1, b, p, q, 1);
            int ans3=query(2*node+1, a, (a+b)/2, p, q, 2)+query(2*node+2, (a+b)/2+1, b, p, q, 0);
            return max(ans1, max(ans2, ans3));
        }else{
            if(pos==2){
                    int ans2=MIN;
                    int ans1=query(2*node+1,(a+b)/2+1, b, p, q, 0);
                    if(ans1==abs(a-b)+1)ans2=ans1+query(2*node+2, a, (a+b)/2, p, q, 0);
                    return max(ans1, ans2);
            }else{
                int ans2=MIN;
                int ans1=query(2*node+2, a, (a+b)/2, p, q, 2);
                if(ans1==abs(a-b)+1)ans2=ans1+query(2*node+1, (a+b)/2+1,b,  p, q, 2);
                return max(ans1, ans2);
            }
        }
}
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();
  y=n;
  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-1);
  for (int k = 0; k < Q; ++k) {
        ll s1=0;
        ll s=query(0, 0, n-1, l[k] , r[k], 1);
        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(int i=0;i<4*4;i++)cout<<tree[i][0]<<" "<<tree[i][1]<<" "<<tree[i][2]<<endl;
  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