oj.uz

Submission #990591

# Submission time Handle Problem Language Result Execution time Memory
990591 2024-05-30T16:54:42 Z AdamGS Dancing Elephants (IOI11_elephants) C++17
100 / 100
 4096 ms 37660 KB 
#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=15e4+7, K=1000;
ll T[LIM], n, L, akt=0, ile;
vector<pair<ll,ll>>B[LIM], nxt[LIM];
void init(int _n, int _L, int _X[]) {
  L=_L; n=_n;
  ile=(n+K-1)/K;
  rep(i, n) T[i]=_X[i];
}
void przelicz(int x) {
  nxt[x].resize(B[x].size());
  if(B[x].size()==0) return;
  int l=B[x].size()-1;
  for(int i=B[x].size()-1; i>=0; --i) {
    while(B[x][i].st+L<B[x][l].st) --l;
    if(l==B[x].size()-1) nxt[x][i]={B[x][i].st+L, 1};
    else nxt[x][i]={nxt[x][l+1].st, nxt[x][l+1].nd+1};
  }
}
void buduj() {
  rep(i, n) {
    B[i].clear();
    nxt[i].clear();
  }
  vector<pair<ll,ll>>P(n);
  rep(i, n) P[i]={T[i], i};
  sort(all(P));
  rep(i, n) B[i/K].pb(P[i]);
  rep(i, ile) przelicz(i);
}
int cnt() {
  ll x=-1;
  int ans=0;
  rep(i, ile) if(B[i].size()) {
    if(x>=B[i].back().st) continue;
    int po=0, ko=B[i].size()-1;
    while(po<ko) {
      int sr=(po+ko)/2;
      if(B[i][sr].st<=x) po=sr+1; else ko=sr;
    }
    ans+=nxt[i][po].nd;
    x=nxt[i][po].st;
  }
  return ans;
}
int update(int i, int y) {
  if(akt%K==0) buduj();
  ++akt;
  int l=0;
  while(B[l].size()==0 || B[l].back().st<T[i]) ++l;
  rep(j, B[l].size()) if(B[l][j].st==T[i]) {
    for(int k=j+1; k<B[l].size(); ++k) B[l][k-1]=B[l][k];
    B[l].pop_back();
    break;
  }
  przelicz(l);
  T[i]=y;
  l=0;
  while(l<ile-1 && (B[l].size()==0 || B[l].back().st<T[i])) ++l;
  vector<pair<ll,ll>>tmp;
  pair<ll,ll>x={T[i], i};
  rep(j, B[l].size()) if(B[l][j]<x) tmp.pb(B[l][j]);
  tmp.pb({T[i], i});
  rep(j, B[l].size()) if(B[l][j]>x) tmp.pb(B[l][j]);
  B[l]=tmp;
  przelicz(l);
  return cnt();
}

Compilation message

elephants.cpp: In function 'void przelicz(int)':
elephants.cpp:24:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     if(l==B[x].size()-1) nxt[x][i]={B[x][i].st+L, 1};
      |        ~^~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
elephants.cpp:59:3: note: in expansion of macro 'rep'
   59 |   rep(j, B[l].size()) if(B[l][j].st==T[i]) {
      |   ^~~
elephants.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int k=j+1; k<B[l].size(); ++k) B[l][k-1]=B[l][k];
      |                    ~^~~~~~~~~~~~
elephants.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
elephants.cpp:70:3: note: in expansion of macro 'rep'
   70 |   rep(j, B[l].size()) if(B[l][j]<x) tmp.pb(B[l][j]);
      |   ^~~
elephants.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
elephants.cpp:72:3: note: in expansion of macro 'rep'
   72 |   rep(j, B[l].size()) if(B[l][j]>x) tmp.pb(B[l][j]);
      |   ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14836 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 481 ms 19076 KB Output is correct
8 Correct 475 ms 19544 KB Output is correct
9 Correct 503 ms 21304 KB Output is correct
10 Correct 632 ms 20852 KB Output is correct
11 Correct 624 ms 20752 KB Output is correct
12 Correct 853 ms 21812 KB Output is correct
13 Correct 629 ms 20556 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14836 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 481 ms 19076 KB Output is correct
8 Correct 475 ms 19544 KB Output is correct
9 Correct 503 ms 21304 KB Output is correct
10 Correct 632 ms 20852 KB Output is correct
11 Correct 624 ms 20752 KB Output is correct
12 Correct 853 ms 21812 KB Output is correct
13 Correct 629 ms 20556 KB Output is correct
14 Correct 714 ms 19980 KB Output is correct
15 Correct 694 ms 20180 KB Output is correct
16 Correct 1389 ms 21912 KB Output is correct
17 Correct 1419 ms 23172 KB Output is correct
18 Correct 1536 ms 23552 KB Output is correct
19 Correct 943 ms 22544 KB Output is correct
20 Correct 1445 ms 23312 KB Output is correct
21 Correct 1361 ms 23924 KB Output is correct
22 Correct 965 ms 22268 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14836 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 481 ms 19076 KB Output is correct
8 Correct 475 ms 19544 KB Output is correct
9 Correct 503 ms 21304 KB Output is correct
10 Correct 632 ms 20852 KB Output is correct
11 Correct 624 ms 20752 KB Output is correct
12 Correct 853 ms 21812 KB Output is correct
13 Correct 629 ms 20556 KB Output is correct
14 Correct 714 ms 19980 KB Output is correct
15 Correct 694 ms 20180 KB Output is correct
16 Correct 1389 ms 21912 KB Output is correct
17 Correct 1419 ms 23172 KB Output is correct
18 Correct 1536 ms 23552 KB Output is correct
19 Correct 943 ms 22544 KB Output is correct
20 Correct 1445 ms 23312 KB Output is correct
21 Correct 1361 ms 23924 KB Output is correct
22 Correct 965 ms 22268 KB Output is correct
23 Correct 2516 ms 35216 KB Output is correct
24 Correct 2575 ms 35352 KB Output is correct
25 Correct 1919 ms 34344 KB Output is correct
26 Correct 2682 ms 33236 KB Output is correct
27 Correct 2797 ms 33284 KB Output is correct
28 Correct 1445 ms 24416 KB Output is correct
29 Correct 1438 ms 24404 KB Output is correct
30 Correct 1455 ms 24616 KB Output is correct
31 Correct 1428 ms 24400 KB Output is correct
32 Correct 2579 ms 32848 KB Output is correct
33 Correct 2495 ms 32040 KB Output is correct
34 Correct 2506 ms 33008 KB Output is correct
35 Correct 2374 ms 37660 KB Output is correct
36 Correct 1692 ms 32596 KB Output is correct
37 Correct 3415 ms 36536 KB Output is correct
38 Correct 2514 ms 32016 KB Output is correct
39 Correct 2526 ms 33104 KB Output is correct
40 Correct 2592 ms 32296 KB Output is correct
41 Correct 4024 ms 34588 KB Output is correct
42 Correct 4096 ms 34704 KB Output is correct