Submission #1308524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308524		nikaa123	Dancing Elephants (IOI11_elephants)	C++20	26 / 100	12 ms	8240 KiB

elephants

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

const int M = 2e5+5;
const int B = 450;
int n,ll;
int a[M];
int t[M];
int fix[M];
int cur;
set<pair<int,int>> s;
vector <vector<pair<int,int>>> v;
vector <pair<int,int>> pos;
pair <int,int> nxt[M];
int nb = (n-1+B-1)/B;

void calc(int j) {
    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;
      }
      nxt[v[j][i].second] = {nxt[v[j][r+1].second].first+1,nxt[v[j][r+1].second].second};
    }
}

void solve() {
  
    v.clear();
    v.resize(M);
    s.clear();
    for (int i = 0; i < n; i++) t[i] = INT_MAX;
    pair<int,int> pos[M];
    for (int i = 0; i < n; i++) {
        pos[i] = {a[i],i};
    }
    sort(pos,pos+n);
    for (int i = 0; i < n; i++) {
        s.insert(pos[i]);
        v[i/B].push_back(pos[i]);
        t[i/B] = min(t[i/B],pos[i].first);
        fix[pos[i].second] = i/B;
    }
    for (int i = 0; i < nb; i++) {
        calc(i);
    }

}

int getans() {
    int cur = -1;
    int res = 0;
    auto it = s.upper_bound({cur,-1});
    while (it != s.end()) {
        int id = (*it).second;
        res += nxt[id].first;
        it = s.upper_bound({nxt[id].second,n+1});
    }
    return res;
}

int findg(int pos) {
    int l = 0; int r = nb-1;
    int id = 0;
    while (l <= r) {
        int mid = (l+r)/2;
        if (t[mid] <= pos) {
            id = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    } 
    return id;
}

void remove(int x) {

    pair<int,int> res = {a[x],x};
    int j = fix[x];
    s.erase(res);
    auto it = find(v[j].begin(),v[j].end(),res);
    v[j].erase(it);
    t[j] = INT_MAX;
    for (auto i:v[j]) {
        t[j] = min(t[j],i.first);
    }

}

void add(int x, int pos) {

    a[x] = pos;
    int j = 0;
    for (;j < nb; j++) {
      if (v[j].back().first > pos) break;
    }
    j--;
    j = max(j,0);
    s.insert({a[x],x});
    v[j].push_back({a[x],x});

    if (v[j].size() > 2*B) {
        solve();
        return;
    }
    sort(v[j].begin(),v[j].end());
    t[j] = min(t[j],a[x]);
    fix[x] = j;
    calc(j);
  
}

void init(int N, int L, int X[]) {
    n = N; ll = L;
    nb = (n-1+B-1)/B;
    for (int i = 0; i < n; i++) {
        a[i] = X[i];
    }
    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: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3