oj.uz

Submission #607605

# Submission time Handle Problem Language Result Execution time Memory
607605 2022-07-26T21:18:31 Z Ronin13 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 4570 ms 19184 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;
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++){

        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();
    cnt++;
    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 676 KB Output is correct
3 Correct 1 ms 684 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 676 KB Output is correct
3 Correct 1 ms 684 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 760 KB Output is correct
6 Correct 1 ms 596 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 676 KB Output is correct
3 Correct 1 ms 684 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 760 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 252 ms 2388 KB Output is correct
8 Correct 274 ms 2728 KB Output is correct
9 Correct 326 ms 6340 KB Output is correct
10 Correct 462 ms 5956 KB Output is correct
11 Correct 362 ms 5896 KB Output is correct
12 Correct 692 ms 6692 KB Output is correct
13 Correct 654 ms 5748 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 676 KB Output is correct
3 Correct 1 ms 684 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 760 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 252 ms 2388 KB Output is correct
8 Correct 274 ms 2728 KB Output is correct
9 Correct 326 ms 6340 KB Output is correct
10 Correct 462 ms 5956 KB Output is correct
11 Correct 362 ms 5896 KB Output is correct
12 Correct 692 ms 6692 KB Output is correct
13 Correct 654 ms 5748 KB Output is correct
14 Correct 373 ms 4336 KB Output is correct
15 Correct 474 ms 4760 KB Output is correct
16 Correct 1130 ms 7248 KB Output is correct
17 Correct 1229 ms 9024 KB Output is correct
18 Correct 1333 ms 8864 KB Output is correct
19 Correct 597 ms 8376 KB Output is correct
20 Correct 1156 ms 9020 KB Output is correct
21 Correct 1148 ms 9116 KB Output is correct
22 Correct 1223 ms 7796 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 676 KB Output is correct
3 Correct 1 ms 684 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 760 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 252 ms 2388 KB Output is correct
8 Correct 274 ms 2728 KB Output is correct
9 Correct 326 ms 6340 KB Output is correct
10 Correct 462 ms 5956 KB Output is correct
11 Correct 362 ms 5896 KB Output is correct
12 Correct 692 ms 6692 KB Output is correct
13 Correct 654 ms 5748 KB Output is correct
14 Correct 373 ms 4336 KB Output is correct
15 Correct 474 ms 4760 KB Output is correct
16 Correct 1130 ms 7248 KB Output is correct
17 Correct 1229 ms 9024 KB Output is correct
18 Correct 1333 ms 8864 KB Output is correct
19 Correct 597 ms 8376 KB Output is correct
20 Correct 1156 ms 9020 KB Output is correct
21 Correct 1148 ms 9116 KB Output is correct
22 Correct 1223 ms 7796 KB Output is correct
23 Correct 2744 ms 18620 KB Output is correct
24 Correct 3201 ms 18444 KB Output is correct
25 Correct 2097 ms 18124 KB Output is correct
26 Correct 2466 ms 17456 KB Output is correct
27 Correct 2810 ms 17340 KB Output is correct
28 Correct 699 ms 5716 KB Output is correct
29 Correct 663 ms 5640 KB Output is correct
30 Correct 679 ms 5720 KB Output is correct
31 Correct 676 ms 5708 KB Output is correct
32 Correct 2734 ms 16844 KB Output is correct
33 Correct 1929 ms 16204 KB Output is correct
34 Correct 2927 ms 17032 KB Output is correct
35 Correct 2137 ms 18656 KB Output is correct
36 Correct 2132 ms 16900 KB Output is correct
37 Correct 3880 ms 19184 KB Output is correct
38 Correct 4167 ms 16088 KB Output is correct
39 Correct 2081 ms 17260 KB Output is correct
40 Correct 4170 ms 16040 KB Output is correct
41 Correct 4395 ms 18748 KB Output is correct
42 Correct 4570 ms 18864 KB Output is correct