Submission #123696

#	Time	Username	Problem	Language	Result	Execution time	Memory
123696		Masterdan	Meetings (IOI18_meetings)	C++14	19 / 100	722 ms	196680 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);
    if(tree[2*node+1][2]>=1 and tree[2*node+2][0]>=1){
        tree[node][1]=tree[2*node+1][2]+tree[2*node+2][0];
        if(tree[2*node+1][0]== tree[2*node+1][1] and tree[2*node+1][1]==tree[2*node+1][2]){
            tree[node][0]=tree[2*node+1][0]+tree[2*node+2][0];
        }else{
                tree[node][0]=tree[2*node+1][0];
        }
        if(tree[2*node+2][0]== tree[2*node+2][1] and tree[2*node+2][1]==tree[2*node+2][2]){
            tree[node][2]=tree[2*node+1][2]+tree[2*node+2][2];
        }else{
               tree[node][2]=tree[2*node+2][2];
        }
    }else {tree[node][1]=max(tree[2*node+1][1], tree[2*node+2][1]);
    tree[node][0]=tree[2*node+1][0];
    tree[node][2]=tree[2*node+2][2];
    }

}
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();
  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]);
        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;
}/*
1
4923 6704
4164 5400
1470 5169
5269 6037
190 4222
5462 5747
305 4920
1974 4457
4922 7175
2207 7712
2782 5118
2185 5196
1807 7139
5103 5319
1186 1353
1661 2413
2497 4482
2747 3849
1503 3279
4885 6281
2635 3023
706 7687
397 6940
2874 5934
96 5032
273 3834
509 1301
1398 7555
2456 6970
2734 7494
6442 6954
801 5867
6061 6269
2796 6808
816 7566
776 5464
787 4473
1280 2285
5166 7879
2804 7222
6738 6921
1306 1716
3372 6308
3451 5759
1023 1112
1396 4814
322 2999
4728 7338
6035 7753
521 1781
967 6799
4110 5925
1793 6323
432 580
959 1253
1352 3538
5178 7528
5384 6781
1912 3349
1339 1648
105 2433
2984 4074
6584 7932
2814 7978
195 7668
1980 7791
140 3367
5434 6437
4009 7983
333 7450
2115 5883
1334 2164
3357 3694
912 2951
74 5101
4356 4690
599 4483
1383 7255
5156 6277
3621 6845
1939 4453
2882 7092
2928 5785
259 739
1514 3975
2372 2597
209 2193
4256 5797
5346 5942
4184 4770
5305 6471
1653 4241
3914 7694
2550 4801
1133 6038
4138 5487
4396 6344
1454 3364
6180 7663
2081 3235
765 5911
1429 6289
5788 6753
220 7721
4991 7570
2818 5277
1727 4245
1240 6557
3800 4630
365 7300
4974 6982
2295 6831
225 4700
5166 6143
3507 6502
1775 5573
739 6399
2298 3260
2975 3466
3214 4814
876 7411
438 3340
2562 3515
3212 3464
432 1481
3163 5487
245 3108
906 3848
2525 3205
583 4200
802 2151
3338 4969
4226 4340
1778 2696
310 5695
2395 7254
2919 4927
2367 7772
1624 6644
270 3036
5719 7465
466
}  // 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;
}*/

Compilation message (stderr)

meetings.cpp:124:2: warning: "/*" within comment [-Wcomment]
 }/*

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