oj.uz

Submission #926856

# Submission time Handle Problem Language Result Execution time Memory
926856 2024-02-14T00:43:13 Z mariaclara Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 28948 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 = 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 21080 KB Output is correct
2 Correct 5 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 21080 KB Output is correct
2 Correct 5 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 5 ms 21136 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21080 KB Output is correct
2 Correct 5 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 5 ms 21136 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 851 ms 22348 KB Output is correct
8 Correct 1000 ms 22792 KB Output is correct
9 Correct 2526 ms 26116 KB Output is correct
10 Correct 3344 ms 26364 KB Output is correct
11 Correct 3373 ms 26252 KB Output is correct
12 Correct 5000 ms 26476 KB Output is correct
13 Correct 3877 ms 26252 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21080 KB Output is correct
2 Correct 5 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 5 ms 21136 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 851 ms 22348 KB Output is correct
8 Correct 1000 ms 22792 KB Output is correct
9 Correct 2526 ms 26116 KB Output is correct
10 Correct 3344 ms 26364 KB Output is correct
11 Correct 3373 ms 26252 KB Output is correct
12 Correct 5000 ms 26476 KB Output is correct
13 Correct 3877 ms 26252 KB Output is correct
14 Correct 2892 ms 23396 KB Output is correct
15 Correct 1592 ms 23568 KB Output is correct
16 Correct 6277 ms 26516 KB Output is correct
17 Correct 8258 ms 28692 KB Output is correct
18 Correct 8445 ms 28948 KB Output is correct
19 Correct 6754 ms 28436 KB Output is correct
20 Correct 7929 ms 28796 KB Output is correct
21 Execution timed out 9031 ms 28752 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21080 KB Output is correct
2 Correct 5 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 5 ms 21136 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 851 ms 22348 KB Output is correct
8 Correct 1000 ms 22792 KB Output is correct
9 Correct 2526 ms 26116 KB Output is correct
10 Correct 3344 ms 26364 KB Output is correct
11 Correct 3373 ms 26252 KB Output is correct
12 Correct 5000 ms 26476 KB Output is correct
13 Correct 3877 ms 26252 KB Output is correct
14 Correct 2892 ms 23396 KB Output is correct
15 Correct 1592 ms 23568 KB Output is correct
16 Correct 6277 ms 26516 KB Output is correct
17 Correct 8258 ms 28692 KB Output is correct
18 Correct 8445 ms 28948 KB Output is correct
19 Correct 6754 ms 28436 KB Output is correct
20 Correct 7929 ms 28796 KB Output is correct
21 Execution timed out 9031 ms 28752 KB Time limit exceeded
22 Halted 0 ms 0 KB -