oj.uz

Submission #926855

# Submission time Handle Problem Language Result Execution time Memory
926855 2024-02-14T00:42:41 Z mariaclara Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 28716 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 = 450;
#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 3 ms 21084 KB Output is correct
2 Correct 3 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 3 ms 21084 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 5 ms 21080 KB Output is correct
5 Correct 5 ms 21084 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 3 ms 21084 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 5 ms 21080 KB Output is correct
5 Correct 5 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 947 ms 22408 KB Output is correct
8 Correct 1050 ms 23128 KB Output is correct
9 Correct 2503 ms 26360 KB Output is correct
10 Correct 2171 ms 26312 KB Output is correct
11 Correct 2127 ms 26068 KB Output is correct
12 Correct 4920 ms 26244 KB Output is correct
13 Correct 2584 ms 26056 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21084 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 5 ms 21080 KB Output is correct
5 Correct 5 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 947 ms 22408 KB Output is correct
8 Correct 1050 ms 23128 KB Output is correct
9 Correct 2503 ms 26360 KB Output is correct
10 Correct 2171 ms 26312 KB Output is correct
11 Correct 2127 ms 26068 KB Output is correct
12 Correct 4920 ms 26244 KB Output is correct
13 Correct 2584 ms 26056 KB Output is correct
14 Correct 3192 ms 23072 KB Output is correct
15 Correct 1725 ms 23636 KB Output is correct
16 Correct 6452 ms 26424 KB Output is correct
17 Correct 8536 ms 28716 KB Output is correct
18 Execution timed out 9026 ms 28672 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21084 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 5 ms 21080 KB Output is correct
5 Correct 5 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 947 ms 22408 KB Output is correct
8 Correct 1050 ms 23128 KB Output is correct
9 Correct 2503 ms 26360 KB Output is correct
10 Correct 2171 ms 26312 KB Output is correct
11 Correct 2127 ms 26068 KB Output is correct
12 Correct 4920 ms 26244 KB Output is correct
13 Correct 2584 ms 26056 KB Output is correct
14 Correct 3192 ms 23072 KB Output is correct
15 Correct 1725 ms 23636 KB Output is correct
16 Correct 6452 ms 26424 KB Output is correct
17 Correct 8536 ms 28716 KB Output is correct
18 Execution timed out 9026 ms 28672 KB Time limit exceeded
19 Halted 0 ms 0 KB -