oj.uz

답안 #299213

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299213 2020-09-14T14:53:09 Z erd1 휴가 (IOI14_holiday) C++14
23 / 100
 92 ms 5504 KB 
#include"holiday.h"

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
typedef int64_t lld;
typedef pair<int, int> pii;

struct node{
  node *L = 0, *R = 0;
  int key;
  lld sum;
  int val, cnt = 1;
  node(int v) : key(rand()), sum(v), val(v) { }
  void up(){ sum = val, cnt = 1; if(L)sum += L->sum, cnt += L->cnt; if(R)sum += R->sum, cnt += R->cnt; }
  pair<node*, node*> splitVal(int s){
    if(val < s){
      if(!L)return{nullptr, this};
      auto p = L->splitVal(s);
      L = p.ss; up();
      return {p.ff, this};
    }else{
      if(!R)return{this, nullptr};
      auto p = R->splitVal(s);
      R = p.ff; up();
      return {this, p.ss};
    }
  }
  pair<node*, node*> splitSize(int k){
    if(k == cnt)return {this, 0};
    if(!k)return {0, this};
    if(k <= (L?L->cnt:0)){
      auto p = L->splitSize(k);
      assert(p.ff->cnt == k);
      L = p.ss; up();
      return {p.ff, this};
    }else{
      auto p = R->splitSize(k-1-(L?L->cnt:0));
      R = p.ff; up();
      assert(cnt == k);
      return {this, p.ss};
    }
  }
  friend node* merge(node* a, node* b){
    if(!a)return b;
    if(!b)return a;
    if(a->key < b->key)
      return a->R = merge(a->R, b), a->up(), a;
    else
      return b->L = merge(a, b->L), b->up(), b;
  }
} *root = 0;

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    srand(time(0));
    lld ans = 0;
    for(int i = 0; i < min(n, d); i++){
      if(!root)root = new node(attraction[i]);
      else{
        auto p = root->splitVal(attraction[i]);
        root = merge(merge(p.ff, new node(attraction[i])), p.ss);
      }
      auto p = root->splitSize(min(i+1, d-i));
      //assert(p.ff->cnt == );
      //cout << d-i << " " << p.ff->sum << endl;
      ans = max(ans, p.ff->sum);
      root = merge(p.ff, p.ss);
    }
    return ans;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Incorrect 1 ms 256 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 5368 KB Output is correct
2 Correct 35 ms 5368 KB Output is correct
3 Correct 41 ms 5504 KB Output is correct
4 Correct 31 ms 5368 KB Output is correct
5 Correct 92 ms 4984 KB Output is correct
6 Correct 22 ms 1792 KB Output is correct
7 Correct 45 ms 3064 KB Output is correct
8 Correct 60 ms 3576 KB Output is correct
9 Correct 15 ms 1408 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Incorrect 3 ms 512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 5368 KB Output is correct
2 Correct 39 ms 5368 KB Output is correct
3 Incorrect 15 ms 896 KB Output isn't correct
4 Halted 0 ms 0 KB -