oj.uz

답안 #547656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
547656 2022-04-11T08:21:48 Z cig32 Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 47 ms 12644 KB 
#include "bubblesort2.h"

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int lmao = 4001000;
int qwq = 1000003;
struct node {
  long long upd = 0, val = 0;
} st[lmao];

void u(int l, int r, int constl, int constr, int idx, long long val) {
  if(l <= constl && constr <= r) {
    st[idx].upd += val;
    st[idx].val += val;
    return;
  }
  int mid = (constl + constr) >> 1;
  st[2*idx+1].upd += st[idx].upd;
  st[2*idx+2].upd += st[idx].upd;
  st[2*idx+1].val += st[idx].upd;
  st[2*idx+2].val += st[idx].upd;
  st[idx].upd = 0;
  if(mid < l || r < constl) u(l, r, mid+1, constr, 2*idx+2, val);
  else if(constr < l || r < mid+1) u(l, r, constl, mid, 2*idx+1, val);
  else {
    u(l, r, constl, mid, 2*idx + 1, val);
    u(l, r, mid+1, constr, 2*idx + 2, val);
  }
  st[idx].val = max(st[2*idx+1].val, st[2*idx+2].val);
}

long long qu(int l, int r, int constl, int constr, int idx) {
  if(l <= constl && constr <= r) return st[idx].val;
  int mid = (constl + constr) >> 1;
  st[2*idx+1].upd += st[idx].upd;
  st[2*idx+2].upd += st[idx].upd;
  st[2*idx+1].val += st[idx].upd;
  st[2*idx+2].val += st[idx].upd;
  st[idx].upd = 0;
  if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
  else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
  else {
    return max(qu(l, r, constl, mid, 2*idx+1), qu(l, r, mid+1, constr, 2*idx+2));
  }
}

void range_add(int l, int r, long long v) {
  u(l, r, 0, qwq, 0, v);
}

long long query_max(int l, int r) {
  return qu(l, r, 0, qwq, 0);
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
  ordered_set ost;
  int N=A.size();
	int Q=X.size();
	std::vector<int> answer(Q);
  set<int> s;
  for(int i=0; i<N; i++) {
    s.insert(A[i]);
    ost.insert({A[i], i});
  }
  for(int i=0; i<Q; i++) s.insert(V[i]);
  unordered_map<int, int> is;
  int nxt = 0;
  for(int x: s) {
    is[x] = nxt++;
  }
  for(int i=0; i<N; i++) A[i] = is[A[i]];
  for(int i=0; i<Q; i++) V[i] = is[V[i]];
  pair<int, int> B[N];
  for(int i=0; i<N; i++) {
    B[i] = {A[i], i};
  }
  sort(B, B+N);
  multiset<pair<int, int> > ms[2*N];
  unordered_map<int, int> ono[2*N];
  for(int i=0; i<N; i++) {
    ms[B[i].first].insert({B[i].second - i, B[i].second});
    //cout << "ms[" << B[i].first << "] insert {" << B[i].second - i << ", "  << B[i].second << "}\n";
    ono[B[i].first][B[i].second] = B[i].second - i;
  }
  for(int i=0; i<2*N; i++) {
    if(ms[i].empty()) {
      range_add(i, i, -1e17);
    }
    else {
      range_add(i, i, (*ms[i].rbegin()).first);
    }
  }
  
  for(int i=0; i<Q; i++) {
    int x = A[X[i]];
    int y = V[i];
    if(A[X[i]] == V[i]) {
      answer[i] = query_max(0, 2*N - 1);
      continue;
    }
    if(x > y) swap(x, y);
    if(x + 1 < y) {
      if(A[X[i]] > V[i]) {
        range_add(x+1, y-1, -1);
      }
      else {
        range_add(x+1, y-1, 1);
      }
    }
    ms[A[X[i]]].erase({ono[A[X[i]]][X[i]], X[i]});
    if(ms[A[X[i]]].empty()) {
      long long ogname = query_max(A[X[i]], A[X[i]]);
      range_add(A[X[i]], A[X[i]], -1e17 - ogname);
    }
    else {
      long long ogname = query_max(A[X[i]], A[X[i]]);
      range_add(A[X[i]], A[X[i]], (*ms[A[X[i]]].rbegin()).first - ogname);
    }
    ost.erase({A[X[i]], X[i]});
    A[X[i]] = V[i];
    ost.insert({A[X[i]], X[i]});
    ms[A[X[i]]].insert({X[i] - ost.order_of_key({A[X[i]], X[i]}), X[i]});
    ono[A[X[i]]][X[i]] = X[i] - ost.order_of_key({A[X[i]], X[i]});
    long long ogname = query_max(A[X[i]], A[X[i]]);
    //cout << "ogname " << ogname <<"\n";
    range_add(A[X[i]], A[X[i]], (*ms[A[X[i]]].rbegin()).first - ogname);
    answer[i] = query_max(0, 2*N - 1);
    //cout << "mengbier updates = " << (*ms[A[X[i]]].rbegin()).first << "\n";
    //cout << "Answer = " << query_max(0, 2*N - 1) << '\n';
    //for(int i=0; i<2*N; i++) cout << (query_max(i, i) == -1e17 ? -1 : query_max(i, i)) << ' ';
    //cout << '\n';
  }
  
	return answer;
}

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 12644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -