oj.uz

Submission #939677

# Submission time Handle Problem Language Result Execution time Memory
939677 2024-03-06T16:34:01 Z Sundavar Dancing Elephants (IOI11_elephants) C++14
100 / 100
 3018 ms 22932 KB 
#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;
typedef pair<int,int> pii;
#define pos first
#define ind second
int at[(int)2e5];
struct buck{
    vector<pii> poz, inf;
};
const int S = 400;
int L, upd = 0;
buck bus[S];
int count(){
    int ans = 0, last = -1;
    for(int i = 0; i < S; i++){
        int j = upper_bound(bus[i].poz.begin(), bus[i].poz.end(), pii(last, 2e9)) - bus[i].poz.begin();
        if(j == bus[i].poz.size()) continue;
        ans += bus[i].inf[j].first, last = bus[i].inf[j].second;
    }
    return ans;
}
void updateBuck(buck& b){
    int last = b.poz.size();
    b.inf.clear(), b.inf.resize(last);
    for(int i = last-1; i >= 0; i--){
        while(b.poz[last-1].pos - b.poz[i].pos > L) last--;
        if(last == b.poz.size()) b.inf[i] = {1, b.poz[i].pos + L};
        else b.inf[i] = {b.inf[last].first + 1, b.inf[last].second};
    }
}
void beoszt(vector<pii>& els){
    for(int i = 0, d = 0, id = 0; i < els.size(); i++){
        if(++d == S) id++, d = 0;
        bus[id].poz.push_back(els[i]);
        at[els[i].ind] = id;
    }
    for(int i = 0; i < S; i++) updateBuck(bus[i]);
}
void remove(int from, int id){
    vector<pii> uj;
    for(pii& a : bus[from].poz)
        if(a.second != id) uj.push_back(a);
    bus[from].poz = uj;
    updateBuck(bus[from]);
}
void insert(int id, pii ele){
    vector<pii> uj;
    at[ele.ind] = id;
    for(pii& a : bus[id].poz){
        if(ele.first < a.first) uj.push_back(ele), ele = {2e9,-1};
        uj.push_back(a);
    }
    if(ele != pii(2e9, -1)) uj.push_back(ele);
    bus[id].poz = uj;
    updateBuck(bus[id]);
}
void init(int N, int l, int x[]){
    L = l;
    vector<pii> els(N);
    for(int i = 0; i < N; i++) els[i] = {x[i], i};
    beoszt(els);
}
int update(int i, int y){
    remove(at[i], i);
    int last = 0;
    for(int i = 0; i < S; i++)
        if(bus[i].poz.size() > 0 && y > bus[i].poz[0].pos) last = i;
    insert(last, pii(y, i));
    if(++upd%S == 0){
        vector<pii> els;
        for(int i = 0; i < S; i++){
            for(pii& a : bus[i].poz) els.push_back(a);
            bus[i].poz.clear();
        }
        beoszt(els);
    }
    return count();
}

/*int main(){
    int N, L, M;
    cin>>N>>L>>M;
    int x[N];
    for(int i = 0; i < N; i++) cin>>x[i];
    init(N,L,x);
    while(M--){
        int i, y;
        cin>>i>>y;
        cout<<update(i, y)<<"\n";
    }
}*/

Compilation message

elephants.cpp: In function 'int count()':
elephants.cpp:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         if(j == bus[i].poz.size()) continue;
      |            ~~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void updateBuck(buck&)':
elephants.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         if(last == b.poz.size()) b.inf[i] = {1, b.poz[i].pos + L};
      |            ~~~~~^~~~~~~~~~~~~~~
elephants.cpp: In function 'void beoszt(std::vector<std::pair<int, int> >&)':
elephants.cpp:34:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i = 0, d = 0, id = 0; i < els.size(); i++){
      |                                   ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 308 ms 9264 KB Output is correct
8 Correct 321 ms 9424 KB Output is correct
9 Correct 438 ms 10628 KB Output is correct
10 Correct 333 ms 10748 KB Output is correct
11 Correct 316 ms 10908 KB Output is correct
12 Correct 600 ms 10860 KB Output is correct
13 Correct 362 ms 10788 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 308 ms 9264 KB Output is correct
8 Correct 321 ms 9424 KB Output is correct
9 Correct 438 ms 10628 KB Output is correct
10 Correct 333 ms 10748 KB Output is correct
11 Correct 316 ms 10908 KB Output is correct
12 Correct 600 ms 10860 KB Output is correct
13 Correct 362 ms 10788 KB Output is correct
14 Correct 472 ms 9620 KB Output is correct
15 Correct 522 ms 9780 KB Output is correct
16 Correct 893 ms 11008 KB Output is correct
17 Correct 979 ms 12416 KB Output is correct
18 Correct 980 ms 12232 KB Output is correct
19 Correct 625 ms 11740 KB Output is correct
20 Correct 970 ms 12024 KB Output is correct
21 Correct 916 ms 12588 KB Output is correct
22 Correct 578 ms 12236 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 308 ms 9264 KB Output is correct
8 Correct 321 ms 9424 KB Output is correct
9 Correct 438 ms 10628 KB Output is correct
10 Correct 333 ms 10748 KB Output is correct
11 Correct 316 ms 10908 KB Output is correct
12 Correct 600 ms 10860 KB Output is correct
13 Correct 362 ms 10788 KB Output is correct
14 Correct 472 ms 9620 KB Output is correct
15 Correct 522 ms 9780 KB Output is correct
16 Correct 893 ms 11008 KB Output is correct
17 Correct 979 ms 12416 KB Output is correct
18 Correct 980 ms 12232 KB Output is correct
19 Correct 625 ms 11740 KB Output is correct
20 Correct 970 ms 12024 KB Output is correct
21 Correct 916 ms 12588 KB Output is correct
22 Correct 578 ms 12236 KB Output is correct
23 Correct 2520 ms 14980 KB Output is correct
24 Correct 2532 ms 19916 KB Output is correct
25 Correct 1966 ms 20080 KB Output is correct
26 Correct 2091 ms 20124 KB Output is correct
27 Correct 2488 ms 19840 KB Output is correct
28 Correct 1268 ms 12056 KB Output is correct
29 Correct 1241 ms 11828 KB Output is correct
30 Correct 1345 ms 12048 KB Output is correct
31 Correct 1230 ms 11840 KB Output is correct
32 Correct 2055 ms 19588 KB Output is correct
33 Correct 1811 ms 19084 KB Output is correct
34 Correct 1845 ms 19556 KB Output is correct
35 Correct 2059 ms 22932 KB Output is correct
36 Correct 2454 ms 19348 KB Output is correct
37 Correct 2533 ms 20692 KB Output is correct
38 Correct 2127 ms 18740 KB Output is correct
39 Correct 2086 ms 19480 KB Output is correct
40 Correct 2061 ms 18920 KB Output is correct
41 Correct 2882 ms 19848 KB Output is correct
42 Correct 3018 ms 20052 KB Output is correct