Submission #990591

#	Time	Username	Problem	Language	Result	Execution time	Memory
990591		AdamGS	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	4096 ms	37660 KiB

elephants

#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 (stderr)

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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3