oj.uz

Submission #926876

# Submission time Handle Problem Language Result Execution time Memory
926876 2024-02-14T01:52:09 Z mariaclara Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 39316 KB 
#pragma GCC optimize ("Ofast")
#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 = 400;
#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);
  }

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

  while(j < n) {
    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;
    }
  }

  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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 3 ms 21080 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 3 ms 21080 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21144 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 3 ms 21080 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21144 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 375 ms 22372 KB Output is correct
8 Correct 472 ms 22796 KB Output is correct
9 Correct 1255 ms 26312 KB Output is correct
10 Correct 1113 ms 26252 KB Output is correct
11 Correct 1089 ms 26504 KB Output is correct
12 Correct 1983 ms 26460 KB Output is correct
13 Correct 1624 ms 26248 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 3 ms 21080 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21144 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 375 ms 22372 KB Output is correct
8 Correct 472 ms 22796 KB Output is correct
9 Correct 1255 ms 26312 KB Output is correct
10 Correct 1113 ms 26252 KB Output is correct
11 Correct 1089 ms 26504 KB Output is correct
12 Correct 1983 ms 26460 KB Output is correct
13 Correct 1624 ms 26248 KB Output is correct
14 Correct 892 ms 23056 KB Output is correct
15 Correct 788 ms 23428 KB Output is correct
16 Correct 3026 ms 26412 KB Output is correct
17 Correct 4159 ms 28864 KB Output is correct
18 Correct 4637 ms 28732 KB Output is correct
19 Correct 3575 ms 28492 KB Output is correct
20 Correct 3866 ms 28776 KB Output is correct
21 Correct 3913 ms 28716 KB Output is correct
22 Correct 3289 ms 28448 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 3 ms 21080 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21144 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 375 ms 22372 KB Output is correct
8 Correct 472 ms 22796 KB Output is correct
9 Correct 1255 ms 26312 KB Output is correct
10 Correct 1113 ms 26252 KB Output is correct
11 Correct 1089 ms 26504 KB Output is correct
12 Correct 1983 ms 26460 KB Output is correct
13 Correct 1624 ms 26248 KB Output is correct
14 Correct 892 ms 23056 KB Output is correct
15 Correct 788 ms 23428 KB Output is correct
16 Correct 3026 ms 26412 KB Output is correct
17 Correct 4159 ms 28864 KB Output is correct
18 Correct 4637 ms 28732 KB Output is correct
19 Correct 3575 ms 28492 KB Output is correct
20 Correct 3866 ms 28776 KB Output is correct
21 Correct 3913 ms 28716 KB Output is correct
22 Correct 3289 ms 28448 KB Output is correct
23 Execution timed out 9100 ms 39316 KB Time limit exceeded
24 Halted 0 ms 0 KB -