Submission #607499

#	Time	Username	Problem	Language	Result	Execution time	Memory
607499		Ronin13	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	21 ms	6224 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;


int n;
int l;
vector <vector <int> > a;
vector <vector <pii> >bl(150001);
vector <int> vec;
int blsize = 500;
vector <int> le,ri;
multiset <ll> st;
void process(int ind){
    bl[ind].resize(a[ind].size());
    int x = bl[ind].size();
    bl[ind][x - 1] = {0, x - 1};
    int cur = x;
    for(int i = x - 2; i >= 0; i--){
        while(a[ind][cur - 1] > a[ind][i] + l){
            cur--;
        }
        if(cur == x){
            bl[ind][i] = {0, i};
        }
        else{
            bl[ind][i] = {bl[ind][cur].f + 1, bl[ind][cur].s};
        }
    }
  //  cout  << 1;
}

void er(int x){
    st.erase(st.find(x));
    for(int i = 0; i < le.size(); i++){
        if(le[i] <= x && ri[i] >= x){
            for(int j = 0; j < a[i].size(); j++){
                if(a[i][j] == x) {
                    a[i].erase(a[i].begin() + j);
                    break;
                }
            }
            //for(int to : a[i]) cout << to << ' ';
            process(i);
            break;
        }
    }
  //  cout << 1;
}

void in(int x){
    st.insert(x);
    for(int i = 0; i < le.size(); i++){
        if(le[i] <= x && ri[i] >= x){
            a[i].pb(x);
            for(int j = a[i].size() - 2; j >= 0; j--){
                if(a[i][j] < x) break;
                swap(a[i][j], a[i][j + 1]);
            }
           // for(int to : a[i]) cout << to << ' ';
            process(i);
            break;
        }
    }
   // cout << 1;
}

int A[150001];

void init(int N, int L, int x[])
{
  n = N;
  l = L;
  for(int i = 0; i < n; i++) A[i] = x[i];
  sort(x, x + n);
  vector <int> cur;
    for(int i = 0; i < n; i++){
        vec.pb(x[i]);
        cur.pb(x[i]);
        st.insert(x[i]);
        if(cur.size() == blsize) a.pb(cur), le.pb(cur[0]), ri.pb(cur.back()), cur.clear();
  }
  if(!cur.empty()){
    a.pb(cur), le.pb(cur[0]), ri.pb(cur.back()), cur.clear();
  }
  ri.back() = INT_MAX;
  for(int i =  0; i < a.size(); i++) process(i);
}

void init1(){
    vector <int> cur;
    le.clear();
    a.clear();
    ri.clear();
    for(int to : st){
        cur.pb(to);
        if(cur.size() == blsize) a.pb(cur), le.pb(cur[0]), ri.pb(cur.back()), cur.clear();
    }
    if(!cur.empty()){
    a.pb(cur), le.pb(cur[0]), ri.pb(cur.back()), cur.clear();
  }
    ri.back() = INT_MAX;
    for(int i = 0; i < a.size(); i++) process(i);
}


int getans(){
    int ans = 0;
    int cur = 0;
    int nx = a[0][0];
    for(int i = 0; i < a.size(); i++){
        if(le[i] > nx || ri[i] < nx) continue;
        int L = -1, R = a[i].size();
        while(L + 1 < R){
            int m = (L + R) / 2;
            if(a[i][m] >= nx) R = m;
            else L = m;
        }
        ans += bl[i][R].f + 1;
        //cout << l << "\n";
        nx = bl[i][R].s + l + 1;
    }
    //cout << 1;
    return ans;
}

int cnt = 0;
int update(int i, int y)
{
    er(A[i]);
    A[i] = y;
    in(A[i]);
    if(cnt % blsize == 0) init1();
    return getans();
}

Compilation message (stderr)

elephants.cpp: In function 'void er(int)':
elephants.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i = 0; i < le.size(); i++){
      |                    ~~^~~~~~~~~~~
elephants.cpp:45:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for(int j = 0; j < a[i].size(); j++){
      |                            ~~^~~~~~~~~~~~~
elephants.cpp: In function 'void in(int)':
elephants.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 0; i < le.size(); i++){
      |                    ~~^~~~~~~~~~~
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:89:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         if(cur.size() == blsize) a.pb(cur), le.pb(cur[0]), ri.pb(cur.back()), cur.clear();
      |            ~~~~~~~~~~~^~~~~~~~~
elephants.cpp:95:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for(int i =  0; i < a.size(); i++) process(i);
      |                   ~~^~~~~~~~~~
elephants.cpp: In function 'void init1()':
elephants.cpp:105:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |         if(cur.size() == blsize) a.pb(cur), le.pb(cur[0]), ri.pb(cur.back()), cur.clear();
      |            ~~~~~~~~~~~^~~~~~~~~
elephants.cpp:111:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i = 0; i < a.size(); i++) process(i);
      |                    ~~^~~~~~~~~~
elephants.cpp: In function 'int getans()':
elephants.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(int i = 0; i < a.size(); i++){
      |                    ~~^~~~~~~~~~
elephants.cpp:117:9: warning: unused variable 'cur' [-Wunused-variable]
  117 |     int cur = 0;
      |         ^~~

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