oj.uz

Submission #926875

# Submission time Handle Problem Language Result Execution time Memory
926875 2024-02-14T01:51:46 Z mariaclara Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 38888 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 = 300;
#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 7 ms 21080 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 3 ms 21124 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 21080 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 3 ms 21124 KB Output is correct
4 Correct 3 ms 21084 KB Output is correct
5 Correct 4 ms 21140 KB Output is correct
6 Correct 5 ms 21084 KB Output is correct
7 Correct 398 ms 22380 KB Output is correct
8 Correct 493 ms 22940 KB Output is correct
9 Correct 1282 ms 26364 KB Output is correct
10 Correct 1272 ms 26260 KB Output is correct
11 Correct 1201 ms 26116 KB Output is correct
12 Correct 2053 ms 26376 KB Output is correct
13 Correct 2062 ms 26360 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 21080 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 3 ms 21124 KB Output is correct
4 Correct 3 ms 21084 KB Output is correct
5 Correct 4 ms 21140 KB Output is correct
6 Correct 5 ms 21084 KB Output is correct
7 Correct 398 ms 22380 KB Output is correct
8 Correct 493 ms 22940 KB Output is correct
9 Correct 1282 ms 26364 KB Output is correct
10 Correct 1272 ms 26260 KB Output is correct
11 Correct 1201 ms 26116 KB Output is correct
12 Correct 2053 ms 26376 KB Output is correct
13 Correct 2062 ms 26360 KB Output is correct
14 Correct 895 ms 22940 KB Output is correct
15 Correct 957 ms 23540 KB Output is correct
16 Correct 3133 ms 26408 KB Output is correct
17 Correct 4246 ms 28916 KB Output is correct
18 Correct 4513 ms 28588 KB Output is correct
19 Correct 4306 ms 28444 KB Output is correct
20 Correct 4040 ms 28600 KB Output is correct
21 Correct 4472 ms 28872 KB Output is correct
22 Correct 4328 ms 28220 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 21080 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 3 ms 21124 KB Output is correct
4 Correct 3 ms 21084 KB Output is correct
5 Correct 4 ms 21140 KB Output is correct
6 Correct 5 ms 21084 KB Output is correct
7 Correct 398 ms 22380 KB Output is correct
8 Correct 493 ms 22940 KB Output is correct
9 Correct 1282 ms 26364 KB Output is correct
10 Correct 1272 ms 26260 KB Output is correct
11 Correct 1201 ms 26116 KB Output is correct
12 Correct 2053 ms 26376 KB Output is correct
13 Correct 2062 ms 26360 KB Output is correct
14 Correct 895 ms 22940 KB Output is correct
15 Correct 957 ms 23540 KB Output is correct
16 Correct 3133 ms 26408 KB Output is correct
17 Correct 4246 ms 28916 KB Output is correct
18 Correct 4513 ms 28588 KB Output is correct
19 Correct 4306 ms 28444 KB Output is correct
20 Correct 4040 ms 28600 KB Output is correct
21 Correct 4472 ms 28872 KB Output is correct
22 Correct 4328 ms 28220 KB Output is correct
23 Execution timed out 9086 ms 38888 KB Time limit exceeded
24 Halted 0 ms 0 KB -