oj.uz

Submission #926857

# Submission time Handle Problem Language Result Execution time Memory
926857 2024-02-14T00:44:05 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 = 300;
#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 4 ms 21080 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 4 ms 21080 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 4 ms 21080 KB Output is correct
4 Correct 5 ms 21084 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 4 ms 21080 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 4 ms 21080 KB Output is correct
4 Correct 5 ms 21084 KB Output is correct
5 Correct 5 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 797 ms 22600 KB Output is correct
8 Correct 940 ms 22904 KB Output is correct
9 Correct 2610 ms 26256 KB Output is correct
10 Correct 2703 ms 26260 KB Output is correct
11 Correct 2610 ms 26508 KB Output is correct
12 Correct 4512 ms 26632 KB Output is correct
13 Correct 4067 ms 26108 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 4 ms 21080 KB Output is correct
4 Correct 5 ms 21084 KB Output is correct
5 Correct 5 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 797 ms 22600 KB Output is correct
8 Correct 940 ms 22904 KB Output is correct
9 Correct 2610 ms 26256 KB Output is correct
10 Correct 2703 ms 26260 KB Output is correct
11 Correct 2610 ms 26508 KB Output is correct
12 Correct 4512 ms 26632 KB Output is correct
13 Correct 4067 ms 26108 KB Output is correct
14 Correct 2555 ms 23452 KB Output is correct
15 Correct 1614 ms 23540 KB Output is correct
16 Correct 5868 ms 26556 KB Output is correct
17 Correct 8119 ms 28712 KB Output is correct
18 Correct 8424 ms 28588 KB Output is correct
19 Correct 7288 ms 28444 KB Output is correct
20 Correct 8114 ms 28812 KB Output is correct
21 Correct 8205 ms 28468 KB Output is correct
22 Correct 6269 ms 28220 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 4 ms 21080 KB Output is correct
4 Correct 5 ms 21084 KB Output is correct
5 Correct 5 ms 21084 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 797 ms 22600 KB Output is correct
8 Correct 940 ms 22904 KB Output is correct
9 Correct 2610 ms 26256 KB Output is correct
10 Correct 2703 ms 26260 KB Output is correct
11 Correct 2610 ms 26508 KB Output is correct
12 Correct 4512 ms 26632 KB Output is correct
13 Correct 4067 ms 26108 KB Output is correct
14 Correct 2555 ms 23452 KB Output is correct
15 Correct 1614 ms 23540 KB Output is correct
16 Correct 5868 ms 26556 KB Output is correct
17 Correct 8119 ms 28712 KB Output is correct
18 Correct 8424 ms 28588 KB Output is correct
19 Correct 7288 ms 28444 KB Output is correct
20 Correct 8114 ms 28812 KB Output is correct
21 Correct 8205 ms 28468 KB Output is correct
22 Correct 6269 ms 28220 KB Output is correct
23 Execution timed out 9047 ms 38840 KB Time limit exceeded
24 Halted 0 ms 0 KB -