이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |