oj.uz

Submission #299338

# Submission time Handle Problem Language Result Execution time Memory
299338 2020-09-14T17:57:57 Z DanerZein Meetings (IOI18_meetings) C++14
36 / 100
 5500 ms 14864 KB 
#include "meetings.h"
#include <bits/stdc++.h>
#define MAX 1000000000000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<ii,ii> iii;
int n;
ll val[100010],tma[400010],tl[400010],tr[400010],len[400010];
void init(int node,int a,int b){
  if(a==b){
    len[node]=1;
    tl[node]=tr[node]=tma[node]=(val[a]==1);
    return;
  }
  ll mid=(a+b)/2;
  init(2*node+1,a,mid);
  init(2*node+2,mid+1,b);
  len[node]=(b-a)+1;
  if(tma[2*node+1]==len[2*node+1]){
    tl[node]=tl[2*node+1]+tl[2*node+2];
  }
  else tl[node]=tl[2*node+1];
  if(tma[2*node+2]==len[2*node+2]){
    tr[node]=tr[2*node+2]+tr[2*node+1];
  }
  else tr[node]=tr[2*node+2];
  tma[node]=max(max(tma[2*node+1],tma[2*node+2]),tr[2*node+1]+tl[2*node+2]);
}
iii query(int node,int a,int b,int l,int r){
  if(a>r or b<l) return iii(ii(0,0),ii(0,-MAX));
  if(l<=a and r>=b){
    return iii(ii(tl[node],tr[node]),ii(len[node],tma[node]));
  }
  int mid=(a+b)/2;
  iii le=query(2*node+1,a,mid,l,r),ri=query(2*node+2,mid+1,b,l,r);
  /*cout<<node<<endl;
  cout<<le.first.first.first<<" "<<le.first.first.second<<" "<<le.first.second.first<<" "<<le.first.second.second<<" "<<le.second<<endl;
  cout<<ri.first.first.first<<" "<<ri.first.first.second<<" "<<ri.first.second.first<<" "<<ri.first.second.second<<" "<<ri.second<<endl;*/
  ll tm=le.second.first+ri.second.first,l1,r1,ma;
  if(le.second.second==le.second.first){
    l1=le.second.second+ri.first.first;
  }
  else l1=le.first.first;
  if(ri.second.second==ri.second.first){
    r1=ri.second.second+le.first.second;
  }
  else r1=ri.first.second;
  ma=max(max(le.second.second,ri.second.second),le.first.second+ri.first.first);
  return iii(ii(l1,r1),ii(tm,ma));
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  bool sw=0;
  for(int i=0;i<H.size();i++){
    if(H[i]>2){
      sw=1;
      break;
    }
    else val[i]=H[i];
  }
  vector<long long> C;
  if(sw==1){
    for(int i=0;i<L.size();i++){
      stack<ii> sl;
      vector<ll> le,ri;
      ll c=0;
      le.push_back(0);
      sl.push(ii(H[L[i]],1));
      for(int j=L[i]+1;j<=R[i];j++){
	ll co=0,t=le.size()-1;
	c=le[t]+H[j-1];
	while(true){
	  if(sl.empty() or sl.top().first>H[j]){
	    sl.push(ii(H[j],co+1));
	    c+=(H[j]*co);
	    break;
	  }
	  co+=sl.top().second;
	  c-=(sl.top().first*sl.top().second);
	  sl.pop();
	}
	le.push_back(c);
      }
      while(!sl.empty()) sl.pop();
      c=0;
      ll t=(R[i]-L[i]);
      ri.resize(t+1);
      ri[t]=0;
      sl.push(ii(H[R[i]],1));
      for(int j=R[i]-1;j>=L[i];j--){
	ll co=0;
	t--;
	c=ri[t+1]+H[j+1];
	while(true){
	  if(sl.empty() or sl.top().first>H[j]){
	    sl.push(ii(H[j],co+1));
	    c+=(H[j]*co);
	    break;
	  }
	  co+=sl.top().second;
	  c-=(sl.top().first*sl.top().second);
	  sl.pop();
	}
	ri[t]=c;
      }
      ll res=MAX;
      t=0;
      for(int j=L[i];j<=R[i];j++){
	ll aux=ll(le[t]+ri[t]+H[j]);
	res=min(res,aux);
	t++;
      }
      C.push_back(res);
    }
  }
  else{
    n=H.size();
    init(0,0,n-1);
    /* for(int i=0;i<25;i++){
      cout<<tl[i]<<" "<<tr[i]<<" "<<len[i]<<" "<<tma[i]<<endl;
    }*/
    for(int i=0;i<L.size();i++){
      iii no=query(0,0,n-1,L[i],R[i]);
      ll ret=((R[i]-L[i])+1)-no.second.second;
      // cout<<no.second.second<<endl;
      ret=no.second.second+(2*ret);
      C.push_back(ret);
    }
  }
  return C;
}

Compilation message

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int i=0;i<H.size();i++){
      |               ~^~~~~~~~~
meetings.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0;i<L.size();i++){
      |                 ~^~~~~~~~~
meetings.cpp:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i=0;i<L.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 340 ms 852 KB Output is correct
11 Correct 1016 ms 796 KB Output is correct
12 Correct 339 ms 880 KB Output is correct
13 Correct 1014 ms 848 KB Output is correct
14 Correct 266 ms 832 KB Output is correct
15 Correct 277 ms 888 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 51 ms 2580 KB Output is correct
3 Correct 160 ms 14832 KB Output is correct
4 Correct 163 ms 14832 KB Output is correct
5 Correct 120 ms 14832 KB Output is correct
6 Correct 153 ms 14864 KB Output is correct
7 Correct 170 ms 14832 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 51 ms 2580 KB Output is correct
3 Correct 160 ms 14832 KB Output is correct
4 Correct 163 ms 14832 KB Output is correct
5 Correct 120 ms 14832 KB Output is correct
6 Correct 153 ms 14864 KB Output is correct
7 Correct 170 ms 14832 KB Output is correct
8 Execution timed out 5506 ms 7408 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 340 ms 852 KB Output is correct
11 Correct 1016 ms 796 KB Output is correct
12 Correct 339 ms 880 KB Output is correct
13 Correct 1014 ms 848 KB Output is correct
14 Correct 266 ms 832 KB Output is correct
15 Correct 277 ms 888 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 51 ms 2580 KB Output is correct
18 Correct 160 ms 14832 KB Output is correct
19 Correct 163 ms 14832 KB Output is correct
20 Correct 120 ms 14832 KB Output is correct
21 Correct 153 ms 14864 KB Output is correct
22 Correct 170 ms 14832 KB Output is correct
23 Execution timed out 5506 ms 7408 KB Time limit exceeded
24 Halted 0 ms 0 KB -