제출 #1308567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308567		nikaa123	코끼리 (Dancing Elephants) (IOI11_elephants)	C++20	50 / 100	345 ms	3328 KiB

elephants

#include<bits/stdc++.h>
#include "elephants.h"
using namespace std;

const int M = 150005;
int B = 400;
int n,ll;
int a[M];
int t[M];
int fix[M];
pair<int,int> pos[M];
set<pair<int,int>> s;
vector <vector<pair<int,int>>> v(700);
pair <int,int> nxt[M];
int nb = (n-1+B-1)/B;
int op;

void calc(int j) {
    if (v[j].empty()) return;
    int r = v[j].size()-1;
    for (int i = v[j].size()-1; i >= 0; i--) {
      int cur = v[j][i].first + ll;
      while (r > i && v[j][r].first  > cur) r--;
      if (r == v[j].size()-1) {
        nxt[v[j][i].second] = {1,cur};
        continue;
      }
      pair<int, int> next_step = nxt[v[j][r + 1].second];
        nxt[v[j][i].second] = {next_step.first + 1, next_step.second};
    }
}

void solve() {
    int total = 0;
    for (int i = 0; i < 700; i++) {
      for (auto p:v[i]) pos[total++] = p;
      v[i].clear();
    }
    for (int i = 0; i < n; i++) {
        v[i/B].push_back(pos[i]);
        fix[pos[i].second] = i/B;
    }
    nb = (n + B - 1) / B;
    for (int i = 0; i < nb; i++) {
        calc(i);
    }
    op = 0;

}

int getans() {
    int cur = -1;
    int res = 0;
    int id = 0;
    while (id < nb) {
        if (v[id].empty() || v[id].back().first <= cur) {
            id++;
            continue;
        }
        auto it = upper_bound(v[id].begin(),v[id].end(),make_pair(cur,INT_MAX));
        int ind = (*it).second;
        res += nxt[ind].first;
        cur = nxt[ind].second;
    }
    return res;
}

void remove(int x) {

    pair<int,int> res = {a[x],x};
    int j = fix[x];
    auto it = lower_bound(v[j].begin(), v[j].end(), make_pair(a[x], x));
    if (it != v[j].end() && (*it).second == x) v[j].erase(it);
    calc(j);

}

void add(int x, int position) {

    a[x] = position;
    int j = max(0, nb - 1);
    for (int i = 0; i < nb - 1; i++) {
        if (!v[i].empty() && position <= v[i].back().first) {
            j = i;
            break;
        }
    }
    auto it = lower_bound(v[j].begin(),v[j].end(),make_pair(a[x],x));
    v[j].insert(it,{a[x],x});
    fix[x] = j;
    calc(j);
    if (++op>=B) {
        solve();
        return;
    }
    
  
}

void init(int N, int L, int X[]) {
    n = N; ll = L;
    nb = 1;
    for (int i = 0; i < n; i++) {
        a[i] = X[i];
        v[0].push_back({X[i],i});
    }
    sort(v[0].begin(),v[0].end());
    solve();
}

int update(int i, int y) {
    remove(i);
    add(i,y);
    int res = getans();
    return res;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3