oj.uz

Submission #926850

# Submission time Handle Problem Language Result Execution time Memory
926850 2024-02-14T00:24:34 Z mariaclara Dancing Elephants (IOI11_elephants) C++17
26 / 100
 3292 ms 27796 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(1, n); 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(1, n); 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(1, n); 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 4 ms 21084 KB Output is correct
2 Correct 4 ms 21132 KB Output is correct
3 Correct 3 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 21132 KB Output is correct
3 Correct 3 ms 21084 KB Output is correct
4 Correct 3 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 4 ms 21132 KB Output is correct
3 Correct 3 ms 21084 KB Output is correct
4 Correct 3 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 875 ms 22604 KB Output is correct
8 Correct 984 ms 24156 KB Output is correct
9 Correct 2511 ms 27796 KB Output is correct
10 Correct 3292 ms 27456 KB Output is correct
11 Incorrect 30 ms 26964 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 4 ms 21132 KB Output is correct
3 Correct 3 ms 21084 KB Output is correct
4 Correct 3 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 875 ms 22604 KB Output is correct
8 Correct 984 ms 24156 KB Output is correct
9 Correct 2511 ms 27796 KB Output is correct
10 Correct 3292 ms 27456 KB Output is correct
11 Incorrect 30 ms 26964 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 4 ms 21132 KB Output is correct
3 Correct 3 ms 21084 KB Output is correct
4 Correct 3 ms 21084 KB Output is correct
5 Correct 4 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 875 ms 22604 KB Output is correct
8 Correct 984 ms 24156 KB Output is correct
9 Correct 2511 ms 27796 KB Output is correct
10 Correct 3292 ms 27456 KB Output is correct
11 Incorrect 30 ms 26964 KB Output isn't correct
12 Halted 0 ms 0 KB -