Submission #752338

#	Time	Username	Problem	Language	Result	Execution time	Memory
752338		aryan12	Sequence (APIO23_sequence)	C++17	13 / 100	403 ms	56244 KiB

sequence

#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 (stderr)

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 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 13 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18