/*
Author: Teoman Ata Korkmaz
*/
#pragma GCC optimize("O3,fast-math,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define int ll
#define ff first
#define ss second
#define endl '\n'
#define spc ' '
#define pb push_back
#define e2(x) (1LL<<(x))
#define lg(x) (__lg(x))
#define gcd(x,y) __gcd(x,y)
#define lcm(x,y) ((x/gcd(x,y))*y)
#define smrt(i) (double(sqrt(8*(i)+1)-1)/2)
#define ssum(x) ((x)*((x)+1)/2)
#define isint(x) (ceil((x))==floor((x)))
#define no cout<<"NO"<<endl
#define yes cout<<"YES"<<endl
#define cendl cout<<endl
#define mset(x,y) memset(x,y,sizeof(x))
#define popcnt(x) __builtin_popcountll(x)
#define clz(x) __builtin_clz(x)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define clock() uint64_t(chrono::high_resolution_clock::now().time_since_epoch().count())
#define compress(x) sort(all(x));x.resize(unique(all(x))-x.begin())
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cerr.tie(NULL);cout<<fixed<<setprecision(0);cerr<<fixed<<setprecision(0)
#define fileio freopen("out.txt","w",stdout);freopen("in.txt","r",stdin)
#define usacoio(s) freopen((s + str(".in")).c_str(), "r", stdin);freopen((s + str(".out")).c_str(), "w", stdout)
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
//using namespace __gnu_pbds;
typedef int_fast32_t i32;
typedef int_fast64_t ll;
typedef long double ldouble;
typedef string str;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef pair<ii,ii> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pair<char,int>> vci;
typedef vector<str> vstr;
typedef map<int,int> mii;
typedef map<char,int> mci;
typedef map<str,int> msi;
typedef map<int,vi> miv;
typedef unordered_map<int,int> umii;
typedef unordered_map<char,int> umci;
typedef unordered_map<str,int> umsi;
typedef unordered_map<int,vi> umiv;
typedef set<int> sti;
typedef set<char> stc;
typedef set<str> sts;
typedef multiset<int> msti;
typedef multiset<char> mstc;
typedef multiset<str> msts;
inline int segsum(int start,int end,int step){
if(end<start)return 0;
return (((end-start)/step+1)*(start+end))>>1;
}
inline int fp(int b,int p,int mod=1e9+7){
int ans=1;
while(p){
if(p&1)ans=(ans*b)%mod;
p>>=1;
b=(b*b)%mod;
}
return ans;
}
template<typename InputIterator,typename T = int>
T accumulate(InputIterator first,InputIterator last,T init = T{}) {
for (; first != last; ++first) {
init += *first;
}
return init;
}
template<typename T,typename T2>inline pair<T,T2> operator+(const pair<T,T2>&a,const pair<T,T2>& b){return {a.ff+b.ff,a.ss+b.ss};}
template<typename T,typename T2>inline pair<T,T2> operator-(const pair<T,T2>&a,const pair<T,T2>& b){return {a.ff-b.ff,a.ss-b.ss};}
template<typename T,typename T2>inline pair<T,T2> operator*(const pair<T,T2>&a,const pair<T,T2>& b){return {a.ff*b.ff,a.ss*b.ss};}
template<typename T,typename T2>inline pair<T,T2> operator/(const pair<T,T2>&a,const pair<T,T2>& b){return {a.ff/b.ff,a.ss/b.ss};}
template<typename T> inline void maxs(T& x,const T& y){return void(x=max(x,y));}
template<typename T> inline void mins(T& x,const T& y){return void(x=min(x,y));}
template<typename T> inline void gcds(T& x,const T& y){return void(x=gcd(x,y));}
template<typename T> inline void lcms(T& x,const T& y){return void(x=lcm(x,y));}
template<typename T,typename T2>inline ostream& operator<<(ostream& os, const pair<T,T2>& p){
os<<"["<<p.ff<<","<<p.ss<<"]";
return os;
}
template<typename T>inline ostream& operator<<(ostream& os,const vector<T>& a) {
for(const T& _:a)os<<_<<' ';
return os;
}
template<typename T>inline ostream& operator<<(ostream& os,const vector<vector<T>>& a) {
for(const vector<T>& _:a)os<<_<<endl;
return os;
}
template<typename T>inline ostream& operator<<(ostream& os,const set<T>& a) {
for(const T& _:a)os<<_<<' ';
return os;
}
template<typename T,typename T2>inline ostream& operator<<(ostream& os,const map<T,T2>& a) {
for(const auto& _:a)os<<_<<' ';
return os;
}
template<typename T,typename T2>inline ostream& operator<<(ostream& os,const unordered_map<T,T2>& a) {
for(const auto& _:a)os<<_<<' ';
return os;
}
template<typename T>inline ostream& operator<<(ostream& os,const queue<T>& b) {
queue<T> a=b;
while(a.size()){
os<<a.front()<<" ";
a.pop();
}
return os;
}
template<typename T>inline ostream& operator<<(ostream& os,const stack<T>& b) {
stack<T> a=b;
while(a.size()){
os<<a.top()<<" ";
a.pop();
}
return os;
}
template<typename T>inline ostream& operator<<(ostream& os,const priority_queue<T>& b) {
priority_queue<T> a=b;
while(a.size()){
os<<a.top()<<" ";
a.pop();
}
return os;
}
template<typename T>inline ostream& operator<<(ostream& os,const priority_queue<T,vector<T>,greater<T>>& b) {
priority_queue<T,vector<T>,greater<T>> a=b;
while(a.size()){
os<<a.top()<<" ";
a.pop();
}
return os;
}
template<typename T,typename T2>inline istream& operator>>(istream& is,pair<T,T2>& p){
is>>(p.ff)>>(p.ss);
return is;
}
template<typename T>inline istream& operator>>(istream& is,vector<T>& a) {
for(T& _:a)is>>_;
return is;
}
inline void print(){cout<<endl;}
template<typename... Args>
inline void print(const Args&... args){
((cout<<args<<' '),...)<<endl;
}
inline void input(){}
template<typename... Args>
inline void input(Args&... args){
(cin>>...>>args);
}
#ifdef ONLINE_JUDGE
template<typename... Args>
inline void debug(const Args&... args){
return void("59");
}
#else
inline void debug(){cerr<<endl;}
template<typename... Args>
inline void debug(const Args&... args){
((cerr<<args<<' '),...)<<endl;
}
#endif
inline void yn(bool b){
if(b)yes;
else no;
}
#define ASSERT(condition, message)\
if(condition){\
cerr<<"Assertion failed: "<<message<<" at "<<__FILE__<<":"<<to_string(__LINE__)<<endl;\
abort();\
}
///////////////////////////////////////////////////////////////////
constexpr int N=3e3+5;
constexpr int A=1e9+5;
constexpr int MOD=1e9+7;
constexpr i32 INF=INT32_MAX;
constexpr ll INFL=INT64_MAX;
constexpr int BLOCK=320;
constexpr ldouble EPS=1e-9;
constexpr int MAXQUERY=100;
constexpr int dx[4]={-1,0,1,0};
constexpr int dy[4]={0,1,0,-1};
mt19937 mt(clock());
///////////////////////////////////////////////////////////////////
int n,m,k,t,q,a,b,x,y,w,ans;
vi v;
inline void subtask1(){
vi a;
for(int i=0;i<n-1;i++){
if(v[i]==v[i+1])a.pb(i);
}
while(q--){
input(x,y);
x--;y--;
auto it=lower_bound(all(a),x);
if(it!=a.end() && *it<y)no;
else yes;
}
}
inline void subtask2(){
}
inline void subtask3(){
while(q--){
input(x,y);
x--;y--;
vi adj[k],vis(k,0);
for(int i=x;i<y;i++){
if((i-x)%2==0){
adj[v[i]].pb(v[i+1]);
}
else{
adj[v[i+1]].pb(v[i]);
}
}
auto dfs=[&adj,&vis](auto&& dfs,int node){
if(vis[node]==1)return false;
if(vis[node]==2)return true;
vis[node]++;
for(auto i:adj[node])if(!dfs(dfs,i))return false;
vis[node]++;
return true;
};
bool flag=0;
for(int i=x;i<=y;i++){
if(!dfs(dfs,v[i])){
flag=1;
break;
}
}
if(flag)no;
else yes;
}
}
inline void subtask4(){
}
inline void solve(void){
input(n,k,q);
v.resize(n);
input(v);
for(auto& i:v)i--;
int n=::n,k=::k,q=::q;
if(k==2) subtask1();
else if(q<=2000) subtask3();
else if(k<=min(n,int(5)))subtask2();
else subtask4();
}
signed main(void){
int start=clock();
fastio;
//usacoio("59");
int _testcase=1;
//cin>>_testcase;
while(_testcase--)solve();
debug("Time elapsed:",(clock()-start)/uint64_t(1e6),"ms");
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
155 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
175 ms |
3496 KB |
Output is correct |
| 3 |
Correct |
164 ms |
3412 KB |
Output is correct |
| 4 |
Correct |
93 ms |
3408 KB |
Output is correct |
| 5 |
Correct |
131 ms |
3408 KB |
Output is correct |
| 6 |
Correct |
157 ms |
3408 KB |
Output is correct |
| 7 |
Correct |
158 ms |
3408 KB |
Output is correct |
| 8 |
Correct |
149 ms |
3440 KB |
Output is correct |
| 9 |
Correct |
134 ms |
3408 KB |
Output is correct |
| 10 |
Correct |
131 ms |
3920 KB |
Output is correct |
| 11 |
Correct |
122 ms |
4276 KB |
Output is correct |
| 12 |
Correct |
115 ms |
4412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
63 ms |
608 KB |
Output is correct |
| 3 |
Correct |
65 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
3 ms |
348 KB |
Output is correct |
| 7 |
Correct |
60 ms |
612 KB |
Output is correct |
| 8 |
Correct |
64 ms |
628 KB |
Output is correct |
| 9 |
Correct |
69 ms |
600 KB |
Output is correct |
| 10 |
Correct |
69 ms |
856 KB |
Output is correct |
| 11 |
Correct |
74 ms |
632 KB |
Output is correct |
| 12 |
Correct |
85 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
155 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
175 ms |
3496 KB |
Output is correct |
| 3 |
Correct |
164 ms |
3412 KB |
Output is correct |
| 4 |
Correct |
93 ms |
3408 KB |
Output is correct |
| 5 |
Correct |
131 ms |
3408 KB |
Output is correct |
| 6 |
Correct |
157 ms |
3408 KB |
Output is correct |
| 7 |
Correct |
158 ms |
3408 KB |
Output is correct |
| 8 |
Correct |
149 ms |
3440 KB |
Output is correct |
| 9 |
Correct |
134 ms |
3408 KB |
Output is correct |
| 10 |
Correct |
131 ms |
3920 KB |
Output is correct |
| 11 |
Correct |
122 ms |
4276 KB |
Output is correct |
| 12 |
Correct |
115 ms |
4412 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
