oj.uz

Submission #607526

# Submission time Handle Problem Language Result Execution time Memory
607526 2022-07-26T19:25:17 Z Ronin13 Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 2572 KB 
#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(15001);
vector <int> vec;
int blsize = 700;
vector <int> le,ri;
multiset <int> st;
void process(int ind){
    bl[ind].resize(a[ind].size());
    int x = bl[ind].size();
    if(x == 0) return;
    bl[ind][x - 1] = {0, a[ind][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, a[ind][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;
  //blsize = sqrt(n);
  for(int i = 0; i < n; i++) A[i] = x[i];
  for(int i = 0; i < n; i++) st.insert(x[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), ri.pb(cur.back()), cur.clear();
        if(le.empty()) le.pb(0);
        else le.pb(ri[ri.size() - 2] + 1);}
    }
    if(!cur.empty()){
        a.pb(cur), ri.pb(cur.back()), cur.clear();
        if(ri.size() > 1){
            le.pb(ri[ri.size() - 2]);
        }
        else le.pb(0);
    }
    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;
        }
        if(R == a[i].size()) continue;
        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

elephants.cpp: In function 'void er(int)':
elephants.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0; i < le.size(); i++){
      |                    ~~^~~~~~~~~~~
elephants.cpp:46:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for(int j = 0; j < a[i].size(); j++){
      |                            ~~^~~~~~~~~~~~~
elephants.cpp: In function 'void in(int)':
elephants.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < le.size(); i++){
      |                    ~~^~~~~~~~~~~
elephants.cpp: In function 'void init1()':
elephants.cpp:95:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |         if(cur.size() == blsize) {a.pb(cur), ri.pb(cur.back()), cur.clear();
      |            ~~~~~~~~~~~^~~~~~~~~
elephants.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0; i < a.size(); i++) process(i);
      |                    ~~^~~~~~~~~~
elephants.cpp: In function 'int getans()':
elephants.cpp:115:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i = 0; i < a.size(); i++){
      |                    ~~^~~~~~~~~~
elephants.cpp:123:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         if(R == a[i].size()) continue;
      |            ~~^~~~~~~~~~~~~~
elephants.cpp:113:9: warning: unused variable 'cur' [-Wunused-variable]
  113 |     int cur = 0;
      |         ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 7297 ms 2268 KB Output is correct
8 Execution timed out 9023 ms 2572 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 7297 ms 2268 KB Output is correct
8 Execution timed out 9023 ms 2572 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 7297 ms 2268 KB Output is correct
8 Execution timed out 9023 ms 2572 KB Time limit exceeded
9 Halted 0 ms 0 KB -