oj.uz

답안 #971830

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971830 2024-04-29T11:16:42 Z GrindMachine 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
50 / 100
 9000 ms 15696 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi

*/

const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
const int B = 315;

#include "elephants.h"

int n,L;
vector<int> a;
set<pii> st;
vector<pii> blocks[N/B+5];
vector<int> block_num, cams, mx_point;

void upd_block(int b){
    if(blocks[b].empty()) return;
    auto &curr = blocks[b];
    int siz = sz(curr);
    int ptr = siz-1;
    rev(i,siz-1,0){
        while(curr[ptr].ff-curr[i].ff > L){
            ptr--;
        }

        int j = curr[i].ss;

        if(ptr+1 == siz){
            cams[j] = 1;
            mx_point[j] = curr[i].ff+L;
        }
        else{
            int k = curr[ptr+1].ss;
            cams[j] = cams[k]+1;
            mx_point[j] = mx_point[k];
        }
    }
}

void build(){
    int ind = 0;
    rep(i,n/B+1){
        blocks[i].clear();
    }

    for(auto [x,i] : st){
        blocks[ind/B].pb({x,i});
        block_num[i] = ind/B;
        ind++;
    }

    rep(b,n/B+1){
        upd_block(b);
    }
}

void init(int n_, int L_, int X[])
{
    n = n_;
    L = L_;
    a = block_num = cams = mx_point = vector<int>(n);
    rep(i,n) a[i] = X[i];
    rep(i,n) st.insert({a[i],i});
    build();
}

int update(int i, int v)
{
    int b = block_num[i];

    {
        auto &curr = blocks[b];
        pii px = {a[i],i};
        curr.erase(find(all(curr),px));
        upd_block(b);
    }

    st.erase({a[i],i});
    a[i] = v;
    st.insert({a[i],i});
    auto it = st.find({a[i],i});

    if(next(it) != st.end()){
        b = block_num[next(it)->ss];
    }
    else if(it != st.begin()){
        b = block_num[prev(it)->ss];
    }
    else{
        b = 0;
    }

    block_num[i] = b;

    {
        auto &curr = blocks[b];
        pii px = {a[i],i};
        curr.insert(upper_bound(all(curr),px),px);
        upd_block(b);
    }

    int mx_reach = -1;
    int ans = 0;

    rep(b,n/B+1){
        auto &curr = blocks[b];
        pii px = {mx_reach+1,-1};
        auto it = upper_bound(all(curr),px);
        if(it == curr.end()){
            conts;
        }

        int j = it->second;
        ans += cams[j];
        mx_reach = mx_point[j];
    }  

    return ans;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6612 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6612 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6612 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 5327 ms 10728 KB Output is correct
8 Correct 7769 ms 11160 KB Output is correct
9 Correct 223 ms 13404 KB Output is correct
10 Correct 2685 ms 14040 KB Output is correct
11 Correct 3076 ms 14044 KB Output is correct
12 Correct 5208 ms 13912 KB Output is correct
13 Correct 2638 ms 13336 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6612 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 5327 ms 10728 KB Output is correct
8 Correct 7769 ms 11160 KB Output is correct
9 Correct 223 ms 13404 KB Output is correct
10 Correct 2685 ms 14040 KB Output is correct
11 Correct 3076 ms 14044 KB Output is correct
12 Correct 5208 ms 13912 KB Output is correct
13 Correct 2638 ms 13336 KB Output is correct
14 Correct 4589 ms 10448 KB Output is correct
15 Correct 225 ms 10584 KB Output is correct
16 Correct 533 ms 12372 KB Output is correct
17 Correct 2135 ms 14572 KB Output is correct
18 Correct 4207 ms 14724 KB Output is correct
19 Correct 6798 ms 15696 KB Output is correct
20 Correct 2163 ms 14876 KB Output is correct
21 Execution timed out 9006 ms 15160 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6612 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 5327 ms 10728 KB Output is correct
8 Correct 7769 ms 11160 KB Output is correct
9 Correct 223 ms 13404 KB Output is correct
10 Correct 2685 ms 14040 KB Output is correct
11 Correct 3076 ms 14044 KB Output is correct
12 Correct 5208 ms 13912 KB Output is correct
13 Correct 2638 ms 13336 KB Output is correct
14 Correct 4589 ms 10448 KB Output is correct
15 Correct 225 ms 10584 KB Output is correct
16 Correct 533 ms 12372 KB Output is correct
17 Correct 2135 ms 14572 KB Output is correct
18 Correct 4207 ms 14724 KB Output is correct
19 Correct 6798 ms 15696 KB Output is correct
20 Correct 2163 ms 14876 KB Output is correct
21 Execution timed out 9006 ms 15160 KB Time limit exceeded
22 Halted 0 ms 0 KB -