oj.uz

Submission #926854

# Submission time Handle Problem Language Result Execution time Memory
926854 2024-02-14T00:40:36 Z mariaclara Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 38840 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 = 350;
#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 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 3 ms 21084 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 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 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 4 ms 21084 KB Output is correct
7 Correct 816 ms 22364 KB Output is correct
8 Correct 934 ms 22888 KB Output is correct
9 Correct 2488 ms 26244 KB Output is correct
10 Correct 2951 ms 26364 KB Output is correct
11 Correct 2926 ms 26264 KB Output is correct
12 Correct 4536 ms 26588 KB Output is correct
13 Correct 3584 ms 26264 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21084 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 4 ms 21084 KB Output is correct
7 Correct 816 ms 22364 KB Output is correct
8 Correct 934 ms 22888 KB Output is correct
9 Correct 2488 ms 26244 KB Output is correct
10 Correct 2951 ms 26364 KB Output is correct
11 Correct 2926 ms 26264 KB Output is correct
12 Correct 4536 ms 26588 KB Output is correct
13 Correct 3584 ms 26264 KB Output is correct
14 Correct 2677 ms 23056 KB Output is correct
15 Correct 1590 ms 23528 KB Output is correct
16 Correct 5968 ms 26248 KB Output is correct
17 Correct 7879 ms 28760 KB Output is correct
18 Correct 7910 ms 28748 KB Output is correct
19 Correct 6918 ms 28468 KB Output is correct
20 Correct 7556 ms 28576 KB Output is correct
21 Correct 7734 ms 28468 KB Output is correct
22 Correct 6857 ms 28456 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21084 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 4 ms 21084 KB Output is correct
7 Correct 816 ms 22364 KB Output is correct
8 Correct 934 ms 22888 KB Output is correct
9 Correct 2488 ms 26244 KB Output is correct
10 Correct 2951 ms 26364 KB Output is correct
11 Correct 2926 ms 26264 KB Output is correct
12 Correct 4536 ms 26588 KB Output is correct
13 Correct 3584 ms 26264 KB Output is correct
14 Correct 2677 ms 23056 KB Output is correct
15 Correct 1590 ms 23528 KB Output is correct
16 Correct 5968 ms 26248 KB Output is correct
17 Correct 7879 ms 28760 KB Output is correct
18 Correct 7910 ms 28748 KB Output is correct
19 Correct 6918 ms 28468 KB Output is correct
20 Correct 7556 ms 28576 KB Output is correct
21 Correct 7734 ms 28468 KB Output is correct
22 Correct 6857 ms 28456 KB Output is correct
23 Execution timed out 9050 ms 38840 KB Time limit exceeded
24 Halted 0 ms 0 KB -