oj.uz

Submission #752338

# Submission time Handle Problem Language Result Execution time Memory
752338 2023-06-02T22:39:04 Z aryan12 Sequence (APIO23_sequence) C++17
13 / 100
 403 ms 56244 KB 
#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int N = 5e5 + 5, INF = 1e18;
pair<int, int> seg[N * 4];
int lazy[N * 4];

void UpdateLazy(int l, int r, int pos)
{
    if(l == r)
    {
        seg[pos].first += lazy[pos];
        seg[pos].second += lazy[pos];
        lazy[pos] = 0;
        return;
    }
    seg[pos].first += lazy[pos];
    seg[pos].second += lazy[pos];
    lazy[pos * 2] += lazy[pos];
    lazy[pos * 2 + 1] += lazy[pos];
    lazy[pos] = 0;
}

void Build(int l, int r, int pos)
{
    seg[pos] = {-r, -l};
    if(l == r) return;
    int mid = (l + r) / 2;
    Build(l, mid, pos * 2);
    Build(mid + 1, r, pos * 2 + 1);
}

void Update(int l, int r, int pos, int ql, int qval)
{
    if(lazy[pos] != 0)
    {
        UpdateLazy(l, r, pos);
    }
    if(ql > r)
    {
        // cout << "Update(" << l << ", " << r << ") out of bounds\n";
        return;
    }
    if(l == r)
    {
        // cout << "Update(" << l << ", " << r << ") total in [1]\n";
        seg[pos].first += qval;
        seg[pos].second += qval;
        return;
    }
    if(l >= ql)
    {
        // cout << "Update(" << l << ", " << r << ") total in [2]\n";
        seg[pos].first += qval;
        seg[pos].second += qval;
        lazy[pos * 2] += qval;
        lazy[pos * 2 + 1] += qval;
        return;
    }
    int mid = (l + r) / 2;
    Update(l, mid, pos * 2, ql, qval);
    Update(mid + 1, r, pos * 2 + 1, ql, qval);
    // cout << "Update(" << l << ", " << r << ") partial\n";
    seg[pos].first = min(seg[pos * 2].first, seg[pos * 2 + 1].first);
    seg[pos].second = max(seg[pos * 2].second, seg[pos * 2 + 1].second);
}

pair<int, int> Query(int l, int r, int pos, int ql, int qr)
{
    if(lazy[pos] != 0)
    {
        UpdateLazy(l, r, pos);
    }
    if(ql <= l && r <= qr)
    {
        return seg[pos];
    }
    if(ql > r || l > qr)
    {
        return {INF, -INF};
    }
    int mid = (l + r) / 2;
    pair<int, int> p1 = Query(l, mid, pos * 2, ql, qr);
    pair<int, int> p2 = Query(mid + 1, r, pos * 2 + 1, ql, qr);
    return {min(p1.first, p2.first), max(p1.second, p2.second)};
}

int32_t sequence(int32_t n, vector<int32_t> a) 
{
    Build(1, n, 1);
    vector<int> occ[n + 1];
    for(int i = 0; i < a.size(); i++)
    {
        occ[a[i]].push_back(i + 1);
    }
    int ans = 1;
    for(int i = 1; i <= n; i++)
    {
        if(occ[i].size() == 0) continue;
        if(occ[i].size() == 1)
        {
            Update(1, n, 1, occ[i][0], 2);
            continue;
        }
        // cout << "occ[i] = {" << occ[i][0] << ", " << occ[i][1] << "}\n";
        // cout << "Updating: [" << occ[i][0] << ", " << n << "]\n";
        Update(1, n, 1, occ[i][0], 1);
        // cout << "Updating: [" << occ[i][1] << ", " << n << "]\n";
        Update(1, n, 1, occ[i][1], 1);
        pair<int, int> p1 = Query(1, n, 1, 1, occ[i][0] - 1);
        if(occ[i][0] == 1)
        {
            p1 = {0, 0};
        }
        pair<int, int> p2 = Query(1, n, 1, occ[i][1], n);
        p1.first = min(p1.first, 0LL);
        // cout << p1.first << " " << p1.second << " " << p2.first << " " << p2.second << "\n";
        if(p2.first + 2 >= p1.first && p2.first - 2 <= p1.second)
        {
            ans = 2;
        }
        if(p2.second + 2 >= p1.first && p2.second - 2 <= p1.second)
        {
            ans = 2;
        }
        // cout << "ans = " << ans << "\n";
        Update(1, n, 1, occ[i][0], 1);
        Update(1, n, 1, occ[i][1], 1);
    }
    return ans;
}

Compilation message

sequence.cpp: In function 'int32_t sequence(int32_t, std::vector<int>)':
sequence.cpp:94:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i = 0; i < a.size(); i++)
      |                    ~~^~~~~~~~~~

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 281 ms 51136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 56244 KB Output is correct
2 Correct 381 ms 56228 KB Output is correct
3 Correct 403 ms 55616 KB Output is correct
4 Correct 347 ms 55628 KB Output is correct
5 Correct 359 ms 52316 KB Output is correct
6 Correct 387 ms 52300 KB Output is correct
7 Correct 312 ms 51084 KB Output is correct
8 Correct 343 ms 50716 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -