QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#489290#9155. 集合WhisperingWillow100 ✓361ms72320kbC++1411.5kb2024-07-24 19:20:272024-07-24 19:20:27

Judging History

你现在查看的是最新测评结果

  • [2024-07-24 19:20:27]
  • 评测
  • 测评结果:100
  • 用时:361ms
  • 内存:72320kb
  • [2024-07-24 19:20:27]
  • 提交

answer

#include <bits/stdc++.h>
/*Pragma*/
/*
#pragma GCC optimize(2)
#pragma GCC optimize(3)  // 火车头
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
*/
/*define*/
#define f(c, a, b) for (register int c = a; c <= b; c++)
#define fd(c, a, b) for (register int c = b; c >= a; c--)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define int long long
#define vpii vector<pi>
#define il inline
#define ri register
#define aint(a) a.begin(), a.end()
#define fr(a) freopen(a, "r", stdin)
#define fo(a) freopen(a, "w", stdout);
#define debug puts("------------------------")
#define lowbit(x) (x & -x)
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define co const

namespace DEBUG{
	const bool DeBug=true;
	int db_cnt;
	il void db() { if (DeBug) puts("--------------"); return; }
	il void db(const auto a) { if (DeBug) ++ db_cnt, std::cerr << "-- | t" << db_cnt << " : " << a << '\n'; return; }
	il void db(const auto a, const auto b) { if (DeBug) ++ db_cnt, std::cerr << "-- | t" << db_cnt << " : " << a << ", " << b << '\n'; return; }
	il void db(const auto a, const auto b, const auto c) { if (DeBug) ++ db_cnt, std::cerr << "-- | t" << db_cnt << " : " << a << ", " << b << ", " << c << '\n'; return; }
	il void db(const auto a, const auto b, const auto c, const auto d) { if (DeBug) ++ db_cnt, std::cerr << "-- | t" << db_cnt << " : " << a << ", " << b << ", " << c << ", " << d << '\n'; return; }
	il void db(const auto a, const auto b, const auto c, const auto d, const auto e) { if (DeBug) ++ db_cnt, std::cerr << "-- | t" << db_cnt << " : " << a << ", " << b << ", " << c << ", " << d << ", " << e << '\n'; return; }
	il void db(const auto *a, const auto len) { if (DeBug) { ++ db_cnt; std::cerr << "-- | t" << db_cnt << " : {"; if (!len) std::cerr << "empty";else { std::cerr << a[1]; for (int i = 2; i <= len; ++ i ) std::cerr << ", " << a[i]; } std::cerr << "}\n"; } return; }
	il void db(const std::pair<auto, auto> a) { if (DeBug) ++ db_cnt, std::cerr << "-- | t" << db_cnt << " : <" << a.first << ", " << a.second << ">\n"; return; }
}

namespace Functions{
	il auto Max(const auto x,const auto y){return x>y?x:y;};
	il auto toMax(auto &x,const auto y){return x=(x>y?x:y);};
	il auto Min(const auto x,const auto y){return x<y?x:y;};
	il auto toMin(auto &x,const auto y){return x=(x<y?x:y);};
	il auto Add(const auto x,const auto y){return x+y;};
	il auto toAdd(auto &x,const auto y){return x=(x+y);};
	il auto Mus(const auto x,const auto y){return x-y;};
	il auto toMus(auto &x,const auto y){return x=(x-y);};
	il auto Mul(const auto x,const auto y){return x*y;};
	il auto toMul(auto &x,const auto y){return x=(x*y);};
	il auto Mul(const auto x,const auto y,const auto p){return (x*y)%p;};
	il auto toMul(auto &x,const auto y,const auto p){return x=((x*y)%p);};
	il auto Div(const auto x,const auto y){return x/y;};
	il auto toDiv(auto &x,const auto y){return x=(x/y);};
	il int Xor(const int x,const int y){return x^y;};
	il int toXor(int &x,const int y){return x=(x^y);};
	il int And(const int x,const int y){return x&y;};
	il int toAnd(int &x,const int y){return x=(x&y);};
	il int Or(const int x,const int y){return x|y;};
	il int toOr(int &x,const int y){return x=(x|y);};
	il int popcnt(const int x){return __builtin_popcount(x);}
	il auto Sqr(const auto x){return x*x;}
	il auto toSqr(auto &x){return x=x*x;}
	il auto Sqr3(const auto x){return x*x*x;}
	il auto toSqr3(auto &x){return x=x*x*x;}
	il auto Sqr4(const auto x){return x*x*x*x;}
	il auto toSqr4(auto &x){return x=x*x*x*x;}
	il auto Sqr(auto x,int res,const int Mod){auto now=x;while(res){if(res&1) toMul(now,x);toMul(x,x);res>>=1;}return now;}
	il auto toSqr(auto x,const int res,const int Mod){return x=(Sqr(x,res,Mod));};
	il auto H_dis(const auto x,const auto y,const auto a,const auto b){return abs(x-a)+abs(y-b);}
	il auto H_dis(const std::pair<auto,auto> x,const std::pair<auto,auto> y){return H_dis(x.first,x.second,y.first,y.second);};
	il auto O_dis(auto x,auto y,auto a,auto b){return (long double)sqrt(Sqr(x-a)+Sqr(y-b));}
	il auto O_dis(const std::pair<auto,auto> x,const std::pair<auto,auto> y){return O_dis(x.first,x.second,y.first,y.second);};
}

namespace FastIO{
	il int read() {ri int ans = 0;ri char c = getchar();ri bool neg = 0;while ((c < '0') | (c > '9')) neg ^= !(c ^ '-'), c = getchar();while ((c >= '0') & (c <= '9')) ans = (ans << 3) + (ans << 1) + c - 48, c = getchar();return neg ? -ans : ans;}
	il void write(ri int x) {if (x < 0)x = -x, putchar('-');if (x > 9)write(x / 10);putchar(x % 10 + '0');}
	il void writes(ri int x) {write(x);putchar(' ');}
	il void writed(ri int x) {write(x);putchar('\n');}
}

namespace Typedef{
	typedef long double lb;
	typedef long long ll;
	typedef std::set<int>::iterator IT;
}

using namespace DEBUG;
using namespace Typedef;
using namespace FastIO;

namespace Mod{
	template<int mod>
	inline unsigned int down(unsigned int x) {
		return x >= mod ? x - mod : x;
	}
	template<int mod>
	struct Modint {
		unsigned int x;
		Modint() = default;
		Modint(unsigned int x) : x(x) {}
		friend std::istream& operator>>(std::istream& in, Modint& a) {return in >> a.x;}
		friend std::ostream& operator<<(std::ostream& out, Modint a) {return out << a.x;}
		friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
		friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
		friend Modint operator*(Modint a, Modint b) {return 1LL * a.x * b.x % mod;}
		friend Modint operator/(Modint a, Modint b) {return a * ~b;}
		friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
		friend Modint operator~(Modint a) {return a ^ (mod - 2);}
		friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
		friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
		friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
		friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
		friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
		friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
		friend Modint& operator++(Modint& a) {return a += 1;}
		friend Modint& operator--(Modint& a) {return a -= 1;}
		friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
		friend bool operator!=(Modint a, Modint b) {return !(a == b);}
		friend bool operator<(Modint a, Modint b) {return (a.x<b.x);}
		friend bool operator>(Modint a, Modint b) {return (a.x>b.x);}
	};
	typedef Modint<998244353> _int;
}

namespace Number{
	const int N = 1e6 + 3;
	int n, m;//**//
	const int INF=2e9,P=1000000007;
	const double eps=1e-6;
}

/*Namespace*/

using namespace Number;
using namespace Mod;
using namespace Functions;
using namespace std;


const int SEED = time(0);  //随机数种子
mt19937 seed(SEED);
namespace Rand {
inline int g(int l, int r) { return uniform_int_distribution<int>(l, r)(seed); }
inline vector<pair<int, int> > tree(int n) {  // n 是点数
	vector<pair<int, int> > edges;
    vector<int> G[n + 2];
    vector<int> fa(n + 2);
    vector<int> prufer(n + 3);
    for (int i = 0; i < n - 2; i++) {
        prufer[i] = g(0, n-1);
    }
    set<int> ac;
    vector<int> prufer_num(n + 11);
    ac.clear();
    edges.clear();
    for (int i = 0; i < n - 2; i++) {
        prufer_num[prufer[i]]++;
    }
    for (int i = 0; i < n; i++) {
        if (prufer_num[i] == 0)
            ac.insert(i);
    }
    for (int i = 0; i < n - 2; i++) {
        int u = prufer[i];
        int v = *ac.begin();
        ac.erase(ac.begin());
        prufer_num[u]--;
        if (prufer_num[u] == 0) {
            ac.insert(u);
        }
        edges.push_back(pair<int, int>(u+1, v+1));
    }
    int u = *ac.begin();
    int v = *ac.rbegin();
    edges.push_back(pair<int, int>(u+1, v+1));
    return edges;
}
inline vector<int> gv(int n,int l,int r){
	vector<int>res;
	f(i,1,n) res.push_back(g(l,r));
	return res;
}
inline vector<pair<int, int> > gpv(int n,int l,int r){
	vector<pair<int, int> >res;
	f(i,1,n) res.push_back(make_pair(g(l,r),g(l,r)));
	return res;
}
inline void print(vector<int> v){
	writed(v.size());
	for(auto i:v) writes(i);
	putchar('\n');
}
inline void print(vector<pair<int,int> > v){
	for(auto i:v) writes(i.first),writed(i.second);
	putchar('\n');
}
inline void print(vector<pair<int,int> > v,vector<int> o){
	int cnt=0;
	for(auto i:v) writes(i.first),writes(i.second),writed(o[cnt++]);
	putchar('\n');
}
}  // namespace Rand
using namespace Rand;

int a[2][N][3]; 

int s[N],t[N];

unordered_map<int,int> p;

int cnt;

inline void add(int x,int y){
	//db(x,y); 
	cnt+=p[x]==0;p[x]+=y;cnt-=p[x]==0;
//	db(cnt);
}
int c[2][N];

inline void upd(int x){
//	db(x);
	if(x<=n){
	//	db(x);
		f(i,0,1){
			f(j,0,2){
				int u=a[i][x][j],d=i?-1:1;
				//db(u,c[i][u],d); 
				add(c[i][u],-d);
				add(c[i][u]^=t[x],d);
			//	db(cnt); 
			} 
		}
	//	db(cnt);
	}
}

namespace Solution{
	inline void solve(){
		n=read();read();m=read();
		f(i,0,1){
			f(k,1,n)
				f(j,0,2){
					a[i][k][j]=read(); 
				}
		}
		f(i,1,n) t[i]=g(1,LONG_LONG_MAX); 
		int r=0;
		f(i,1,n){
			while(r<=n&&(!cnt)) upd(++r);
			s[i]=r-1;
			upd(i);
		}
		f(i,1,m){
			int l=read();
			puts(s[l]>=read()?"Yes":"No");
		}
		return;
	}
	inline int Solve(){

		return 0;
	}
}


signed main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int T=1;

	while(T--)
	    Solution::solve();


	//while(T--)
	//    std::cout<<Solution::Solve()<<'\n';


    return 0;
}

详细


Pretests

Pretest #1:

score: 5
Accepted
time: 2ms
memory: 11872kb

Pretest #2:

score: 5
Accepted
time: 0ms
memory: 11868kb

Pretest #3:

score: 5
Accepted
time: 2ms
memory: 12076kb

Pretest #4:

score: 5
Accepted
time: 2ms
memory: 11924kb

Pretest #5:

score: 5
Accepted
time: 0ms
memory: 11860kb

Pretest #6:

score: 5
Accepted
time: 2ms
memory: 11876kb

Pretest #7:

score: 5
Accepted
time: 0ms
memory: 11916kb

Pretest #8:

score: 5
Accepted
time: 2ms
memory: 11904kb

Pretest #9:

score: 5
Accepted
time: 6ms
memory: 11840kb

Pretest #10:

score: 5
Accepted
time: 7ms
memory: 11844kb

Pretest #11:

score: 5
Accepted
time: 322ms
memory: 68748kb

Pretest #12:

score: 5
Accepted
time: 276ms
memory: 66308kb

Pretest #13:

score: 5
Accepted
time: 0ms
memory: 12252kb

Pretest #14:

score: 5
Accepted
time: 3ms
memory: 12332kb

Pretest #15:

score: 5
Accepted
time: 46ms
memory: 12240kb

Pretest #16:

score: 5
Accepted
time: 41ms
memory: 12376kb

Pretest #17:

score: 5
Accepted
time: 18ms
memory: 18104kb

Pretest #18:

score: 5
Accepted
time: 15ms
memory: 19140kb

Pretest #19:

score: 5
Accepted
time: 361ms
memory: 69144kb

Pretest #20:

score: 5
Accepted
time: 352ms
memory: 70052kb

Final Tests

Test #1:

score: 5
Accepted
time: 2ms
memory: 11812kb

Test #2:

score: 5
Accepted
time: 0ms
memory: 11920kb

Test #3:

score: 5
Accepted
time: 0ms
memory: 11864kb

Test #4:

score: 5
Accepted
time: 0ms
memory: 11868kb

Test #5:

score: 5
Accepted
time: 1ms
memory: 11920kb

Test #6:

score: 5
Accepted
time: 1ms
memory: 11884kb

Test #7:

score: 5
Accepted
time: 1ms
memory: 11952kb

Test #8:

score: 5
Accepted
time: 0ms
memory: 11952kb

Test #9:

score: 5
Accepted
time: 6ms
memory: 11908kb

Test #10:

score: 5
Accepted
time: 10ms
memory: 11900kb

Test #11:

score: 5
Accepted
time: 291ms
memory: 68604kb

Test #12:

score: 5
Accepted
time: 284ms
memory: 64516kb

Test #13:

score: 5
Accepted
time: 3ms
memory: 12492kb

Test #14:

score: 5
Accepted
time: 0ms
memory: 12284kb

Test #15:

score: 5
Accepted
time: 45ms
memory: 14356kb

Test #16:

score: 5
Accepted
time: 49ms
memory: 12316kb

Test #17:

score: 5
Accepted
time: 22ms
memory: 16148kb

Test #18:

score: 5
Accepted
time: 19ms
memory: 19040kb

Test #19:

score: 5
Accepted
time: 348ms
memory: 66056kb

Test #20:

score: 5
Accepted
time: 359ms
memory: 72320kb

Extra Test:

score: 0
Extra Test Passed