QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#489290 | #9155. 集合 | WhisperingWillow | 100 ✓ | 361ms | 72320kb | C++14 | 11.5kb | 2024-07-24 19:20:27 | 2024-07-24 19:20:27 |
Judging History
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;
}
Details
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