oj.uz

Submission #926874

# Submission time Handle Problem Language Result Execution time Memory
926874 2024-02-14T01:49:28 Z mariaclara Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 39048 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);
  }

  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 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 5 ms 21084 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 5 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 3 ms 21080 KB Output is correct
7 Correct 384 ms 22396 KB Output is correct
8 Correct 493 ms 22896 KB Output is correct
9 Correct 1189 ms 26128 KB Output is correct
10 Correct 1215 ms 26356 KB Output is correct
11 Correct 1165 ms 26256 KB Output is correct
12 Correct 2001 ms 26556 KB Output is correct
13 Correct 1889 ms 26256 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 5 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 3 ms 21080 KB Output is correct
7 Correct 384 ms 22396 KB Output is correct
8 Correct 493 ms 22896 KB Output is correct
9 Correct 1189 ms 26128 KB Output is correct
10 Correct 1215 ms 26356 KB Output is correct
11 Correct 1165 ms 26256 KB Output is correct
12 Correct 2001 ms 26556 KB Output is correct
13 Correct 1889 ms 26256 KB Output is correct
14 Correct 873 ms 22940 KB Output is correct
15 Correct 874 ms 23520 KB Output is correct
16 Correct 2915 ms 26256 KB Output is correct
17 Correct 4172 ms 28696 KB Output is correct
18 Correct 3947 ms 28732 KB Output is correct
19 Correct 3716 ms 28572 KB Output is correct
20 Correct 3925 ms 28648 KB Output is correct
21 Correct 4019 ms 28668 KB Output is correct
22 Correct 3803 ms 28868 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 5 ms 21084 KB Output is correct
4 Correct 4 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 3 ms 21080 KB Output is correct
7 Correct 384 ms 22396 KB Output is correct
8 Correct 493 ms 22896 KB Output is correct
9 Correct 1189 ms 26128 KB Output is correct
10 Correct 1215 ms 26356 KB Output is correct
11 Correct 1165 ms 26256 KB Output is correct
12 Correct 2001 ms 26556 KB Output is correct
13 Correct 1889 ms 26256 KB Output is correct
14 Correct 873 ms 22940 KB Output is correct
15 Correct 874 ms 23520 KB Output is correct
16 Correct 2915 ms 26256 KB Output is correct
17 Correct 4172 ms 28696 KB Output is correct
18 Correct 3947 ms 28732 KB Output is correct
19 Correct 3716 ms 28572 KB Output is correct
20 Correct 3925 ms 28648 KB Output is correct
21 Correct 4019 ms 28668 KB Output is correct
22 Correct 3803 ms 28868 KB Output is correct
23 Execution timed out 9087 ms 39048 KB Time limit exceeded
24 Halted 0 ms 0 KB -