oj.uz

Submission #926871

# Submission time Handle Problem Language Result Execution time Memory
926871 2024-02-14T01:33:07 Z mariaclara Dancing Elephants (IOI11_elephants) C++17
0 / 100
 5 ms 21100 KB 
#pragma GCC optimize ("O3")
#include "elephants.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5+5;
const int x = 350;
#define all(x) x.begin(), x.end()
#define mk make_pair
#define pb push_back
#define f first
#define s second

int n, l, at, group[MAXN], pos[MAXN];
pii dp[MAXN], inter_gp[MAXN]; // qtd de cameras e pos onde termina 
set<pii> ele, ele_gp[MAXN];

void init(int N, int L, int X[]) {
  n = N;
  l = L;

  for(int i = 0; i < n; i++)
    ele.insert({X[i], i}), pos[i] = X[i];

  for(int i = 0; i < n; i++)
    group[i] = i/x, ele_gp[i/x].insert({X[i],i});
  group[n] = (n-1)/x+1;

  for(int i = 0; i <= (n-1)/x; i++)
    inter_gp[i] = mk((*ele_gp[i].begin()).f, (*ele_gp[i].rbegin()).f);

  for(int i = n-1; i >= 0; i--) {
    auto ptr = ele.upper_bound(mk(X[i] + l, 1e9));
    if(ptr == ele.end()) { dp[i] = mk(0, i); continue; }
    int j = (*ptr).s;
    if(group[i] < group[j]) dp[i] = mk(0, i);
    else dp[i] = mk(1 + dp[j].f, dp[j].s);
  }

}

void att(int G) {
  vector<int> ord;

  for(auto [v, i] : ele_gp[G])
    ord.pb(i);

  reverse(all(ord));

  for(int j = 0, k = 0; j < ord.size(); j++) {
    while(pos[ord[k]] >= pos[ord[j]] + l) k++;

    if(k == 0) dp[ord[j]] = mk(0, ord[j]);
    else dp[ord[j]] = mk(1 + dp[ord[k-1]].f, dp[ord[k-1]].s);
  }
}

int update(int i, int y) {
  at++;

  if(at == x) {
    vector<int> ord;
    ele.erase({pos[i], i});
    ele.insert({y,i});
    pos[i] = y;

    for(int j = 0; j <= (n-1)/x; j++)
      ele_gp[j].clear();

    int cnt = 0;
    for(auto [v, j] : ele)
      group[j] = cnt/x, ord.pb(j), ele_gp[cnt/x].insert({v, j}), cnt++;

    for(int j = 0; j <= (n-1)/x; j++)
      inter_gp[j] = mk((*ele_gp[j].begin()).f, (*ele_gp[j].rbegin()).f);

    reverse(all(ord));

    for(int j = 0, k = 0; j < ord.size(); j++) {
      while(pos[ord[k]] >= pos[ord[j]] + l) k++;

      if(k == 0 or group[ord[k-1]] > group[ord[j]]) dp[ord[j]] = mk(0, ord[j]);
      else dp[ord[j]] = mk(1 + dp[ord[k-1]].f, dp[ord[k-1]].s);
    }

    at = 0;
  }
  else {
    int G1 = group[i];
    ele.erase({pos[i], i});
    ele_gp[G1].erase({pos[i], i});

    int ptr = upper_bound(inter_gp, inter_gp+(n-1)/x+1, mk(y,(int)2e9)) - inter_gp;
    if(ptr > 0) ptr--;
    int G2 = ptr;
    group[i] = G2;
    pos[i] = y;
    ele.insert({y,i});
    inter_gp[G2].s = max(inter_gp[G2].s, y);
    ele_gp[G2].insert({y, i});

    if(G2 < G1) swap(G1, G2);

    att(G2);
    if(G2 != G1) att(G1);
  }

  /*cout << "at = " << at << endl;
  for(int j = 0; j <= (n-1)/x; j++) {
    cout << "group " << j << ":\n";
    for(auto [v, k] : ele_gp[j])
      cout << v << " " << k << " " << dp[k].f << " " << dp[k].s << " " << group[k] << endl;
  }*/

  int j = (*ele.begin()).s, r = 0;

  while(j < n) {
    //cout << j << " ";
    if(dp[j].f > 0) {
      r += dp[j].f;
      j = dp[j].s;
    }
    else {
      auto ptr = ele.upper_bound(mk(pos[j] + l, 1e9));
      r++;
      if(ptr == ele.end()) break;
      j = (*ptr).s;
    }
  }
  //cout << endl;

  return r;
}

// g++ elephants.cpp grader.cpp -o elephants

Compilation message

elephants.cpp: In function 'void att(int)':
elephants.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int j = 0, k = 0; j < ord.size(); j++) {
      |                         ~~^~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:82:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int j = 0, k = 0; j < ord.size(); j++) {
      |                           ~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 4 ms 21100 KB Output is correct
3 Incorrect 3 ms 21084 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 4 ms 21100 KB Output is correct
3 Incorrect 3 ms 21084 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 4 ms 21100 KB Output is correct
3 Incorrect 3 ms 21084 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 4 ms 21100 KB Output is correct
3 Incorrect 3 ms 21084 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 4 ms 21100 KB Output is correct
3 Incorrect 3 ms 21084 KB Output isn't correct
4 Halted 0 ms 0 KB -