oj.uz

Submission #277041

# Submission time Handle Problem Language Result Execution time Memory
277041 2020-08-21T01:51:29 Z Masterdan Meetings (IOI18_meetings) C++14
36 / 100
 1201 ms 432048 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 209280 KB Output is correct
2 Correct 146 ms 209376 KB Output is correct
3 Correct 131 ms 209400 KB Output is correct
4 Correct 139 ms 209412 KB Output is correct
5 Correct 136 ms 209480 KB Output is correct
6 Correct 132 ms 209400 KB Output is correct
7 Correct 131 ms 209400 KB Output is correct
8 Correct 146 ms 209380 KB Output is correct
9 Correct 134 ms 209376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 209280 KB Output is correct
2 Correct 146 ms 209376 KB Output is correct
3 Correct 131 ms 209400 KB Output is correct
4 Correct 139 ms 209412 KB Output is correct
5 Correct 136 ms 209480 KB Output is correct
6 Correct 132 ms 209400 KB Output is correct
7 Correct 131 ms 209400 KB Output is correct
8 Correct 146 ms 209380 KB Output is correct
9 Correct 134 ms 209376 KB Output is correct
10 Correct 682 ms 209604 KB Output is correct
11 Correct 606 ms 209700 KB Output is correct
12 Correct 711 ms 209656 KB Output is correct
13 Correct 508 ms 209712 KB Output is correct
14 Correct 787 ms 209592 KB Output is correct
15 Correct 705 ms 209836 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12928 KB Output is correct
2 Correct 53 ms 14392 KB Output is correct
3 Correct 179 ms 19564 KB Output is correct
4 Correct 256 ms 19560 KB Output is correct
5 Correct 141 ms 19564 KB Output is correct
6 Correct 179 ms 19800 KB Output is correct
7 Correct 192 ms 19564 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12928 KB Output is correct
2 Correct 53 ms 14392 KB Output is correct
3 Correct 179 ms 19564 KB Output is correct
4 Correct 256 ms 19560 KB Output is correct
5 Correct 141 ms 19564 KB Output is correct
6 Correct 179 ms 19800 KB Output is correct
7 Correct 192 ms 19564 KB Output is correct
8 Runtime error 1201 ms 432048 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 209280 KB Output is correct
2 Correct 146 ms 209376 KB Output is correct
3 Correct 131 ms 209400 KB Output is correct
4 Correct 139 ms 209412 KB Output is correct
5 Correct 136 ms 209480 KB Output is correct
6 Correct 132 ms 209400 KB Output is correct
7 Correct 131 ms 209400 KB Output is correct
8 Correct 146 ms 209380 KB Output is correct
9 Correct 134 ms 209376 KB Output is correct
10 Correct 682 ms 209604 KB Output is correct
11 Correct 606 ms 209700 KB Output is correct
12 Correct 711 ms 209656 KB Output is correct
13 Correct 508 ms 209712 KB Output is correct
14 Correct 787 ms 209592 KB Output is correct
15 Correct 705 ms 209836 KB Output is correct
16 Correct 8 ms 12928 KB Output is correct
17 Correct 53 ms 14392 KB Output is correct
18 Correct 179 ms 19564 KB Output is correct
19 Correct 256 ms 19560 KB Output is correct
20 Correct 141 ms 19564 KB Output is correct
21 Correct 179 ms 19800 KB Output is correct
22 Correct 192 ms 19564 KB Output is correct
23 Runtime error 1201 ms 432048 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -