Submission #698605

#	Time	Username	Problem	Language	Result	Execution time	Memory
698605		feilinlp	Alternating Heights (CCO22_day1problem1)	C++17	0 / 25	318 ms	71896 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;

    // for (int i=0; i<q; i++)
    // {
    //     cout << query[i].f.f << " " << query[i].f.s << endl;
    // }

    while (pos<q) //check every query
    {
        // cout << __LINE__ << endl;
        int ff=query[pos].f.f;
        while (!to_reset.empty()) //reset the array
        {
            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 < ff) //find next left
        {
            // cout << __LINE__ << endl;
            left++;
        }
        right=left;

        bool fail=false;
        int x=1; //right > right+1
        while (query[pos].f.f == left) //when l still the same process all r
        {
            // cout << pos << endl;
            // cout << __LINE__ << endl;
            if (fail || a[right] == a[right+1])
            {
                fail=true;
                // cout << __LINE__ << endl;
                ans[query[pos].s]=0;
                pos++;
            }
            else if (sign[a[right]][a[right+1]]==0 || sign[a[right]][a[right+1]]==x)
            {
                // if (right==4)
                //     cout << sign[0][1] << " " << x << endl;
                // cout << sign[0][1] << " " << sign[1][0] << endl;
                // cout << __LINE__ << endl;
                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]));
                right++;
            }
            else
            {
                fail=true;
                // cout << __LINE__ << endl;
                ans[query[pos].s]=0;
                pos++;
            }
            x=-x;

            if (right==query[pos].f.s && !fail)
            {
                // cout << __LINE__ << endl;
                ans[query[pos].s]=1;
                pos++;
            }
            // cout << __LINE__ << endl;
        }
        // cout << __LINE__ << endl;
    }

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

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