oj.uz

Submission #926853

# Submission time Handle Problem Language Result Execution time Memory
926853 2024-02-14T00:37:27 Z mariaclara Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 44112 KB 
#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(auto j : ord) {
    auto ptr = ele.upper_bound(mk(pos[j] + l, 1e9));
    if(ptr == ele.end()) { dp[j] = mk(0, j); continue; }
    int k = (*ptr).s;
    if(group[j] < group[k]) dp[j] = mk(0, j);
    else dp[j] = mk(1 + dp[k].f, dp[k].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 : ord) {
      auto ptr = ele.upper_bound(mk(pos[j] + l, 1e9));
      if(ptr == ele.end()) { dp[j] = mk(0, j); continue; }
      int k = (*ptr).s;
      if(group[j] < group[k]) dp[j] = mk(0, j);
      else dp[j] = mk(1 + dp[k].f, dp[k].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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21120 KB Output is correct
2 Correct 4 ms 21084 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 5 ms 21120 KB Output is correct
2 Correct 4 ms 21084 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 21084 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 5 ms 21120 KB Output is correct
2 Correct 4 ms 21084 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 21084 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 949 ms 22404 KB Output is correct
8 Correct 1053 ms 22832 KB Output is correct
9 Correct 2599 ms 26272 KB Output is correct
10 Correct 3584 ms 26124 KB Output is correct
11 Correct 3456 ms 26252 KB Output is correct
12 Correct 4937 ms 27908 KB Output is correct
13 Correct 3983 ms 27388 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21120 KB Output is correct
2 Correct 4 ms 21084 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 21084 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 949 ms 22404 KB Output is correct
8 Correct 1053 ms 22832 KB Output is correct
9 Correct 2599 ms 26272 KB Output is correct
10 Correct 3584 ms 26124 KB Output is correct
11 Correct 3456 ms 26252 KB Output is correct
12 Correct 4937 ms 27908 KB Output is correct
13 Correct 3983 ms 27388 KB Output is correct
14 Correct 2914 ms 24592 KB Output is correct
15 Correct 1692 ms 24928 KB Output is correct
16 Correct 6453 ms 28328 KB Output is correct
17 Correct 8550 ms 30732 KB Output is correct
18 Correct 8675 ms 30704 KB Output is correct
19 Correct 6952 ms 31004 KB Output is correct
20 Correct 8361 ms 30696 KB Output is correct
21 Correct 8301 ms 30644 KB Output is correct
22 Correct 7079 ms 30236 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21120 KB Output is correct
2 Correct 4 ms 21084 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 21084 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 949 ms 22404 KB Output is correct
8 Correct 1053 ms 22832 KB Output is correct
9 Correct 2599 ms 26272 KB Output is correct
10 Correct 3584 ms 26124 KB Output is correct
11 Correct 3456 ms 26252 KB Output is correct
12 Correct 4937 ms 27908 KB Output is correct
13 Correct 3983 ms 27388 KB Output is correct
14 Correct 2914 ms 24592 KB Output is correct
15 Correct 1692 ms 24928 KB Output is correct
16 Correct 6453 ms 28328 KB Output is correct
17 Correct 8550 ms 30732 KB Output is correct
18 Correct 8675 ms 30704 KB Output is correct
19 Correct 6952 ms 31004 KB Output is correct
20 Correct 8361 ms 30696 KB Output is correct
21 Correct 8301 ms 30644 KB Output is correct
22 Correct 7079 ms 30236 KB Output is correct
23 Execution timed out 9097 ms 44112 KB Time limit exceeded
24 Halted 0 ms 0 KB -