oj.uz

Submission #1066137

# Submission time Handle Problem Language Result Execution time Memory
1066137 2024-08-19T15:19:39 Z jerzyk Comparing Plants (IOI20_plants) C++17
5 / 100
 454 ms 74420 KB 
#include <bits/stdc++.h>
#include "plants.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
int n, k;
int drz[2 * N], laz[2 * N];
int tab[N];
ll jp[N][20];
ll jp2[N][20];
vector<int> cur;

inline void Push(int v)
{
    drz[v * 2] += laz[v]; laz[v * 2] += laz[v];
    drz[v * 2 + 1] += laz[v]; laz[v * 2 + 1] += laz[v];
    laz[v] = 0;
}

int Find(int v, int a, int b, int pz, int kz)
{
    if(b < pz || a > kz || drz[v] > 0) return -1;
    if(v > N)
    {
        drz[v] = II;
        return v - N;
    }
    Push(v);
    int ans = Find(v * 2 + 1, (a + b) / 2 + 1, b, pz, kz);
    drz[v] = min(drz[v * 2], drz[v * 2 + 1]);
    if(ans != -1) return ans;
    ans = Find(v * 2, a, (a + b) / 2, pz, kz);
    drz[v] = min(drz[v * 2], drz[v * 2 + 1]);
    return ans;
}

void Add(int v, int a, int b, int pz, int kz)
{
    if(b < pz || a > kz) return;
    if(a >= pz && b <= kz)
    {
        --drz[v]; --laz[v];
        return;
    }
    Add(v * 2, a, (a + b) / 2, pz, kz);
    Add(v * 2 + 1, (a + b) / 2 + 1, b, pz, kz);
    drz[v] = min(drz[v * 2], drz[v * 2 + 1]) + laz[v];
}

int F(int i)
{
    int a = -1;
    if(i > 1)
        a = Find(1, 0, N - 1, max(i - k, 1), i - 1);
    if(a != -1) return a;
    if(i <= k)
        a = Find(1, 0, N - 1, n - (k - i + 1), n);
    return a;
}

void D(int i)
{
    if(i > 1)
        Add(1, 0, N - 1, max(i - k, 1), i - 1);
    if(i <= k)
        Add(1, 0, N - 1, n - (k - i), n);
}

inline int Dis(int i, int j)
{
    if(i < j)
        return j - i;
    return n - (i - j);
}

inline int J(int i, ll d)
{
    i += d % (ll)n;
    if(i > n) i -= n;
    if(i < 1) i += n;
    return i;
}

void DoJP1()
{
    //cerr << n << " " << k << "\n";
    set<pair<int, int>> zbi;
    set<pair<int, int>>::iterator it;
    for(int i = 2; i <= k + 1; ++i)
        zbi.insert(make_pair(tab[i], i));
    for(int i = 1; i <= n; ++i)
    {
        it = zbi.lower_bound(make_pair(tab[i], 0));
        //cerr << "jp1 " << (*it).nd << "\n";
        if(it == zbi.end())
            jp[i][0] = 0;
        else
            jp[i][0] = Dis(i, (*it).nd);
        if(i < n)
            zbi.erase(make_pair(tab[i + 1], i + 1));
        int nxt = J(i, k + 1);
        zbi.insert(make_pair(tab[nxt], nxt));
    }

    for(int j = 1; j <= 19; ++j)
        for(int i = 1; i <= n; ++i)
            jp[i][j] = jp[i][j - 1] + jp[J(i, jp[i][j - 1])][j - 1];
    /*for(int i = 1; i <= n; ++i)
        cerr << jp[i][0] << " ";
    cerr << "\n";*/
}

void DoJP2()
{
    set<pair<int, int>> zbi;
    set<pair<int, int>>::iterator it;
    for(int i = n; i > n - k; --i)
        zbi.insert(make_pair(tab[i], i));
    for(int i = 1; i <= n; ++i)
    {
        it = zbi.lower_bound(make_pair(tab[i], 0));
        //cerr << "jp2: " << (*it).nd << "\n";
        if(it == zbi.end())
            jp2[i][0] = 0;
        else
            jp2[i][0] = -Dis((*it).nd, i);
        int pr = J(i, -k);
        zbi.erase(make_pair(tab[pr], pr));
        
        zbi.insert(make_pair(tab[i], i));
    }

    for(int j = 1; j <= 19; ++j)
        for(int i = 1; i <= n; ++i)
            jp2[i][j] = jp2[i][j - 1] + jp2[J(i, jp2[i][j - 1])][j - 1];
    //for(int i = 1; i <= n; ++i)
        //cerr << jp2[i][0] << " ";
    //cerr << "\n";
}

void init(int KK, vector<int> r) 
{
    n = r.size(); 
    k = KK - 1;

    for(int i = 0; i < n; ++i)
        drz[i + N + 1] = r[i];
    drz[N] = II;
    for(int i = n + 1; i < N; ++i)
        drz[i + N] = II;
    for(int i = N - 1; i >= 1; --i)
        drz[i] = min(drz[i * 2], drz[i * 2 + 1]);
    for(int i = n; i >= 1; --i)
    {
        vector<int> cur;
        cur.pb(Find(1, 0, N - 1, 1, n));
        int x = F(cur.back());
        while(x != -1)
        {
            cur.pb(x);
            x = F(x);
        }
        //cerr << "cur: " << i << "\n";
        for(int j = cur.size() - 1; j >= 0; --j)
        {
            //cerr << cur[j] << " ";
            tab[cur[j]] = i;
            D(cur[j]);
            --i;
        }
        //cerr << "\n";
        ++i;
    }
    //for(int i = 1; i <= n; ++i)
        //cerr << tab[i] << " ";
    //cerr << "\n";
    //cerr << "xd\n";
    //cerr << k << "\n";
    DoJP1();
    DoJP2();
}

int Jump(int a, int d)
{
    for(int i = 19; i >= 0; --i)
        if(jp[a][i] <= (ll)d)
        {
            d -= jp[a][i];
            a = J(a, jp[a][i]);
        }
    return a;
}

int Jump2(int a, int d)
{
    for(int i = 19; i >= 0; --i)
        if(-jp2[a][i] <= (ll)d)
        {
            d += jp2[a][i];
            a = J(a, jp2[a][i]);
        }
    return a;
}

bool Cp(int x, int y)
{
    int a = Jump(x, Dis(x, y));
    int b = Jump2(x, -Dis(x, y) + n);
    //cerr << -Dis(x, y) + n << "\n";
    if(a == y || b == y) return true;
    if(Dis(a, y) <= k && tab[a] < tab[y]) return true;
    if(Dis(y, b) <= k && tab[b] < tab[y]) return true;
    return false;
}

int compare_plants(int x, int y) 
{
    ++x; ++y;
    int answer = 0;
    if(tab[x] < tab[y] && Cp(x, y))
        answer = -1;
    if(tab[x] > tab[y] && Cp(y, x))
        answer = 1;
    //cerr << "que: " << x << " " << y << " tab: " << tab[x] << " " << tab[y] << " ans: " << answer << "\n";
    return answer;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 83 ms 6140 KB Output is correct
7 Correct 119 ms 14160 KB Output is correct
8 Correct 317 ms 74320 KB Output is correct
9 Correct 316 ms 74224 KB Output is correct
10 Correct 383 ms 74316 KB Output is correct
11 Correct 409 ms 74400 KB Output is correct
12 Correct 425 ms 74288 KB Output is correct
13 Correct 454 ms 74420 KB Output is correct
14 Correct 420 ms 74220 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 3 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 5 ms 2908 KB Output is correct
7 Correct 64 ms 9044 KB Output is correct
8 Incorrect 3 ms 2652 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 3 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 5 ms 2908 KB Output is correct
7 Correct 64 ms 9044 KB Output is correct
8 Incorrect 3 ms 2652 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2408 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 86 ms 7660 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Incorrect 2 ms 2520 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Incorrect 2 ms 2652 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 83 ms 6140 KB Output is correct
7 Correct 119 ms 14160 KB Output is correct
8 Correct 317 ms 74320 KB Output is correct
9 Correct 316 ms 74224 KB Output is correct
10 Correct 383 ms 74316 KB Output is correct
11 Correct 409 ms 74400 KB Output is correct
12 Correct 425 ms 74288 KB Output is correct
13 Correct 454 ms 74420 KB Output is correct
14 Correct 420 ms 74220 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 3 ms 2392 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 2 ms 2396 KB Output is correct
20 Correct 5 ms 2908 KB Output is correct
21 Correct 64 ms 9044 KB Output is correct
22 Incorrect 3 ms 2652 KB Output isn't correct
23 Halted 0 ms 0 KB -