oj.uz

답안 #528471

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
528471 2022-02-20T10:49:32 Z N1NT3NDO Magneti (COCI21_magneti) C++17
0 / 110
 1000 ms 1540 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = (int)2e5 + 5;
int n, l[N], r[N], q, nxt[N], mn[N][22], lg[N], t[8 * N], mod[8 * N], mx, up[N][22];
vector<int> vec;

bool in(const pair<int, int> a, const pair<int, int> b)
{
    return (b.fi >= a.fi && b.sd <= a.sd);
}

int get(int l, int r)
{
    int t = lg[r - l + 1];
    return min(mn[l][t], mn[r - (1 << t) + 1][t]);
}

void push(int v, int tl, int tr)
{
    if (tl == tr) return;
    mod[v + v] = min(mod[v + v], mod[v]);
    mod[v + v + 1] = min(mod[v + v + 1], mod[v]);
    t[v + v] = min(t[v + v], mod[v]);
    t[v + v + 1] = min(t[v + v + 1], mod[v]);
}

void build(int v, int tl, int tr)
{
    if (tl == tr)
    {
        t[v] = n + 1;
        mod[v] = n + 1;
        return;
    }

    int m = (tl + tr) >> 1;
    build(v + v, tl, m);
    build(v + v + 1, m + 1, tr);
    t[v] = min(t[v + v], t[v + v + 1]);
    mod[v] = n + 1;
}

int get(int v, int tl, int tr, int l, int r)
{
    push(v, tl, tr);
    if (tl > tr || tl > r || tr < l) return n + 1;

    if (tl >= l && tr <= r)
      return t[v];

    //push(v, tl, tr);
    int m = (tl + tr) >> 1;
    return min(get(v + v, tl, m, l, r), get(v + v + 1, m + 1, tr, l, r));
}

void upd(int v, int tl, int tr, int l, int r, int val)
{
    push(v, tl, tr);
    if (tl > tr || tl > r || tr < l) return;

    if (tl >= l && tr <= r)
    {
        t[v] = min(t[v], val);
        mod[v] = min(mod[v], val);
        //push(v, tl, tr);
        return;
    }

    int m = (tl + tr) >> 1;
    //push(v, tl, tr);
    upd(v + v, tl, m, l, r, val);
    upd(v + v + 1, m + 1, tr, l, r, val);
    t[v] = min(t[v + v], t[v + v + 1]);
}

bool cmp(pair<int, int> a, pair<int, int> b)
{
    return a.fi <= b.fi;
}

int get_ans(int a, int b)
{
    int ans = 0;
    for(int i = 21; i >= 0; i--)
      {
          if (up[a][i] <= b)
            a = up[a][i], ans += (1 << i);
      }

    return ans + 1;
}

int get_ans1(int le, int ri)
{
    int i = le, ans = 0;
    while(i <= ri)
    {
        //int mn = get(i, nxt[i] - 1);
        //mn = min(mn, ri + 1);
        i = nxt[i];
        ans++;
    }

    return ans;
}

void solve()
{
    //cin >> n;
    vec.clear();
    for(int i = 1; i <= n; i++)
      for(int j = 0; j <= 21; j++)
        up[i][j] = 0;
    lg[1] = 0;
    for(int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    for(int i = 1; i <= n; i++)
    {
        //cin >> l[i] >> r[i];
        vec.pb(l[i]);
        vec.pb(r[i]);
    }

    sort(all(vec));
    mx = 1;
    vec.erase(unique(all(vec)), vec.end());
    for(int i = 1; i <= n; i++)
    {
        l[i] = lower_bound(all(vec), l[i]) - vec.begin(); l[i]++;
        r[i] = lower_bound(all(vec), r[i]) - vec.begin(); r[i]++;
        mx = max(mx, l[i]);
        mx = max(mx, r[i]);
    }

    build(1, 1, mx);
    for(int i = n; i >= 1; i--)
    {

        int val = get(1, 1, mx, l[i], r[i]);
        nxt[i] = val;

        mn[i][0] = nxt[i];
        upd(1, 1, mx, l[i], r[i], i);
    }

    for(int i = 1; (1 << i) <= n; i++)
    {
        for(int j = 1; j + (1 << i) - 1 <= n; j++)
          mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]);
    }

    for(int i = 1; i <= n; i++)
    {
        nxt[i] = get(i, nxt[i] - 1);
        up[i][0] = nxt[i];
    }

    for(int j = 1; j <= 21; j++)
    {
        for(int i = 1; i <= n; i++)
            up[i][j] = up[up[i][j - 1]][j - 1];
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= 21; j++)
          if (up[i][j] == 0)
            up[i][j] = n + 1;
    }

    //cout << "!" << ' ' << n << endl;
    //for(int i = 1; i <= n; i++) cout << i << ' ' << nxt[i] - 1 << endl;

}

int main()
{
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    srand(time(0));
    while(true)
    {
        n = rand() % 20 + 1;
        for(int i = 1; i <= n; i++)
        {
            l[i] = rand() % 1000 + 1;
            r[i] = rand() % 1000 + 1;
            if (l[i] > r[i]) swap(l[i], r[i]);
        }

        int a = rand() % n + 1, b = rand() % n + 1;
        if (a > b) swap(a, b);
        solve();
        //cout << n << endl;
        //for(int i = 1; i <= n; i++) cout << l[i] << ' ' << r[i] << endl;
        cout << get_ans(a, b) << ' ' << get_ans1(a, b) << endl;
        if (get_ans(a, b) != get_ans1(a, b))
        {
            cout << "NO" << endl;
            cout << get_ans(a, b) << ' ' << get_ans1(a, b) << endl;
            cout << n << endl;
            for(int i = 1; i <= n; i++) cout << l[i] << r[i] << endl;
            return 0;
        }
        else cout << "YES" << endl;
    }

}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1083 ms 1364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1084 ms 1528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1073 ms 1540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1083 ms 1364 KB Time limit exceeded
2 Halted 0 ms 0 KB -