Submission #698606

#	Time	Username	Problem	Language	Result	Execution time	Memory
698606		feilinlp	Alternating Heights (CCO22_day1problem1)	C++17	4 / 25	354 ms	35540 KiB

Main

#include <iostream>
#include <algorithm>
#include <utility>
#include <cstring>
#include <vector>
#define f first
#define s second

using namespace std;

bool comp( pair < pair <int, int> , int> a, pair < pair <int, int> , int> b)
{
    if (a.f.f != b.f.f)
        return a.f.f < b.f.f;
    else
        return a.f.s < b.f.s;
}

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);

    int n, k, q;
    cin >> n >> k >> q;
    int a[n], sign[k][k];
    memset(sign, 0, sizeof(sign));

    for (int i=0; i<n; i++)
    {
        cin >> a[i];
        a[i]--;
    }
    // cout << __LINE__ << endl;
    
    pair < pair <int, int>, int>  query[q];
    int ans[q];
    for (int i=0; i<q; i++)
    {
        // cout << __LINE__ << endl;
        ans[i]=-1;
        cin >> query[i].f.f >> query[i].f.s;
        query[i].f.f--;
        query[i].f.s--;
        query[i].s = i;
    }
    sort(query, query+q, comp);
    // cout << __LINE__ << endl;

    int left=0, right=0, pos=0;
    vector < pair <int, int> > to_reset;

    while (pos < q) // make sure left different already
    {
        while (!to_reset.empty())
        {
            sign[to_reset.back().f][to_reset.back().s]=0;
            sign[to_reset.back().s][to_reset.back().f]=0;
            to_reset.pop_back();
        }

        while (left < query[pos].f.f)
        {
            left++;
        }
        right=left;

        int x=1;
        bool fail=false;
        while (left == query[pos].f.f)
        {
            if (fail)
            {
                ans[query[pos].s]=0;
                pos++;
                continue;
            }
            
            while (right < query[pos].f.s)
            {
                if (a[right]==a[right+1])
                {
                    // cout << "?";
                    fail=true;
                    break;
                }
                else if (sign[a[right]][a[right+1]]==0)
                {
                    sign[a[right]][a[right+1]]=x;
                    sign[a[right+1]][a[right]]=-x;
                    to_reset.push_back(make_pair(a[right], a[right+1]));
                }
                else if (sign[a[right]][a[right+1]]!=x)
                {
                    // cout << a[right] << a[right+1] << x;
                    // cout << "?";
                    fail=true;
                    break;
                }
                right++;
                x=-x;
            }
            
            if (!fail && right == query[pos].f.s)
            {
                ans[query[pos].s]=1;
                pos++;
            }
        }
    }

    for (int i=0; i<q; i++)
    {
        if (ans[i])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8