oj.uz

Submission #138299

# Submission time Handle Problem Language Result Execution time Memory
138299 2019-07-29T17:10:10 Z Angelos Meetings (IOI18_meetings) C++14
17 / 100
 120 ms 8016 KB 
#include "meetings.h"
#include <iostream>
#include <vector>
#define l 2*cur
#define r ((2*cur)+1)
#define mid ((a+b)/2)
#define MAXN 100100

using namespace std;
typedef long long ll;
struct str{
    int mx;
    int mxl;
    int mxr;
    int all;
}tree[4*MAXN];

vector<int> H;

str doleaf(int o){
    str ret;
    if(o == 1){
        ret.mx = 1;
        ret.mxl = 1;
        ret.mxr = 1;
        ret.all = 1;
    }
    else{
        ret.mx = 0;
        ret.mxl = 0;
        ret.mxr = 0;
        ret.all = 0;
    }

    return ret;
}

str mergee(str ll , str rr){
    str ret;
    if(ll.all && rr.all) ret.all = 1;
    else ret.all = 0;

    if(ll.all) ret.mxl = ll.mxl + rr.mxl;
    else ret.mxl = ll.mxl;

    if(rr.all) ret.mxr = ll.mxr + rr.mxr;
    else ret.mxr = rr.mxr;

    ret.mx = max(ll.mxr + rr.mxl , max(ll.mx , rr.mx));

    return ret;
}

void build(int cur , int a , int b){
    if(a == b){
        //cout <<cur << " " <<  a << " " << H[a] << endl;
        tree[cur] = doleaf(H[a]);
        return;
    }

    build(l , a , mid);
    build(r , mid+1 , b);

    tree[cur] = mergee(tree[l] , tree[r]);
}

str query(int cur , int a , int b , int i , int j){
    if(a >= i && b<=j) return tree[cur];
    if(mid < i) return query(r , mid+1, b , i , j);
    if(mid+1 > j) return query(l ,a , mid , i , j);

    str qq1 = query(l ,a , mid , i , j) , qq2 = query(r , mid+1 , b , i , j);
    return mergee(qq1,qq2);
}

std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> L,
                                     std::vector<int> R) {
  H = h;
  int N = h.size();
  int Q = L.size();
  std::vector<long long> C(Q);

  build(1,0,N-1);
  //for(int i=0; i<4*N; i++) {cout << i << " ";}
  //cout << endl;

  //for(int i=0; i<4*N; i++) cout << tree[i].mx << " " ;

  for (int j = 0; j < Q; ++j) {
    int hh = query(1 , 0 , N-1 , L[j] , R[j]).mx;
    C[j]= (ll)(hh + (R[j] - L[j] + 1 - hh)*2);
    //if(R[j] == L[j]) C[j] = 0;
  }
  return C;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 38 ms 1880 KB Output is correct
3 Correct 114 ms 7944 KB Output is correct
4 Correct 115 ms 7928 KB Output is correct
5 Correct 87 ms 7952 KB Output is correct
6 Correct 109 ms 8016 KB Output is correct
7 Correct 120 ms 7996 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 38 ms 1880 KB Output is correct
3 Correct 114 ms 7944 KB Output is correct
4 Correct 115 ms 7928 KB Output is correct
5 Correct 87 ms 7952 KB Output is correct
6 Correct 109 ms 8016 KB Output is correct
7 Correct 120 ms 7996 KB Output is correct
8 Incorrect 119 ms 7960 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -