QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#818879 | #9873. Last Chance: Threads of Despair | icealsoheat | WA | 45ms | 5844kb | C++17 | 5.9kb | 2024-12-18 10:27:44 | 2024-12-18 10:27:51 |
Judging History
answer
#pragma GCC optimize(3) //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int mod=998244353;
const int MX=0x3f3f3f3f3f3f3f3f;
//inline int read() //快读
//{
// int xr=0,F=1; char cr;
// while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
// while(cr>='0'&&cr<='9')
// xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
// return xr*F;
//}
//void write(int x) //快写
//{
// if(x<0) putchar('-'),x=-x;
// if(x>9) write(x/10); putchar(x%10+'0');
//}
// 比 unordered_map 更快的哈希表
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// struct chash {
// int operator()(int x) const { return x ^ RANDOM; }
// };
// typedef gp_hash_table<int, int, chash> hash_t;
template<int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(ll x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt power(MInt a, ll b) {
MInt res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
ll v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
constexpr int P = 998244353; //这里为自动模数
using mint = MInt<P>; //mint是其定理的类型
int n,m;
int a[500005];
int b[500005];
void icealsoheat(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i];
int cnt=0;
sort(a+1,a+1+n);
sort(b+1,b+1+m);
int id;
id=1;
int op=0;
for(int i=n;i>=1;i--){
op++;
if(a[i]==1)break;
}
queue<int>q;
while(id<=n&&cnt>=a[id]-1){
cnt++;
id++;
}
for(int i=1;i<=m;i++){
if(op+cnt<b[i]){
puts("No");
return;
}
op+=q.size();
if(b[i]>cnt-q.size()){
op-=b[i]-cnt+q.size();
}
int g=cnt+1;
cnt++;
while(id<=n&&cnt>=a[id]-1){
cnt++;
id++;
}
if(b[i]>cnt)q.push(b[i]);
while(q.size()){
if(q.front()<cnt){
int need=q.front()-g;
need=max(0ll,need);
op+=min(need,cnt-q.front());
q.pop();
}
else{
break;
}
}
}
puts("Yes");
}
signed main(){
ios::sync_with_stdio(false); //int128不能用快读!!!!!!
cin.tie();
cout.tie();
int _yq;
_yq=1;
cin>>_yq;
while(_yq--){
icealsoheat();
}
}
//
//⠀⠀⠀ ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
//⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
//⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
//⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
//⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
//⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
//⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
//⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
//
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5840kb
input:
3 3 2 1 1 4 2 6 3 2 1 1 4 2 7 2 1 100 100 2
output:
Yes No Yes
result:
ok 3 token(s): yes count is 2, no count is 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 5600kb
input:
3 7 1 1 1 1 1 1 1 1 9 5 2 3 4 5 6 7 1 6 5 3 3 4 5 6 7 1 5 7
output:
No No Yes
result:
ok 3 token(s): yes count is 1, no count is 2
Test #3:
score: 0
Accepted
time: 1ms
memory: 5540kb
input:
4 1 1 1 1 1 1 1 2 1 1 2 1 1 1 2 2
output:
Yes Yes Yes No
result:
ok 4 token(s): yes count is 3, no count is 1
Test #4:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
18 1 2 1 1 1 1 2 1 2 1 1 2 1 1 3 1 2 1 2 2 1 2 1 3 2 1 2 1 3 3 1 2 2 1 1 1 2 2 1 2 1 2 2 1 3 1 2 2 2 2 1 2 2 2 3 1 2 2 3 3 1 2 3 1 1 1 2 3 1 2 1 2 3 1 3 1 2 3 2 2 1 2 3 3 2 1 2 3 3 3
output:
Yes Yes Yes Yes No No Yes Yes No No No No Yes No No No No No
result:
ok 18 token(s): yes count is 7, no count is 11
Test #5:
score: 0
Accepted
time: 1ms
memory: 5640kb
input:
18 2 1 1 1 1 2 1 1 1 2 2 1 1 1 3 2 1 1 2 1 2 1 2 1 2 2 1 2 1 3 2 1 1 3 1 2 1 1 3 2 2 1 3 1 3 2 1 2 2 1 2 1 2 2 2 2 1 2 2 3 2 1 2 3 1 2 1 3 2 2 2 1 2 3 3 2 1 3 3 1 2 1 3 3 2 2 1 3 3 3
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes No Yes Yes No
result:
ok 18 token(s): yes count is 15, no count is 3
Test #6:
score: 0
Accepted
time: 1ms
memory: 5576kb
input:
525 2 3 1 1 1 1 1 2 3 1 1 1 2 1 2 3 1 1 1 3 1 2 3 1 1 1 4 1 2 3 1 1 5 1 1 2 3 1 1 2 2 1 2 3 1 1 3 1 2 2 3 1 1 1 2 4 2 3 1 1 2 1 5 2 3 1 1 3 3 1 2 3 1 1 4 3 1 2 3 1 1 3 5 1 2 3 1 1 4 4 1 2 3 1 1 4 5 1 2 3 1 1 1 5 5 2 3 1 1 2 2 2 2 3 1 1 2 3 2 2 3 1 1 2 2 4 2 3 1 1 2 5 2 2 3 1 1 3 2 3 2 3 1 1 3 2 4 2 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes No No No No No No No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes No No No No No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 525 token(s): yes count is 202, no count is 323
Test #7:
score: 0
Accepted
time: 0ms
memory: 5564kb
input:
525 3 2 1 1 1 1 1 3 2 1 1 1 2 1 3 2 1 1 1 3 1 3 2 1 1 1 1 4 3 2 1 1 1 1 5 3 2 1 1 1 2 2 3 2 1 1 1 2 3 3 2 1 1 1 4 2 3 2 1 1 1 2 5 3 2 1 1 1 3 3 3 2 1 1 1 4 3 3 2 1 1 1 5 3 3 2 1 1 1 4 4 3 2 1 1 1 5 4 3 2 1 1 1 5 5 3 2 1 1 2 1 1 3 2 2 1 1 2 1 3 2 2 1 1 1 3 3 2 1 2 1 1 4 3 2 1 1 2 5 1 3 2 1 1 2 2 2 3 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No No No Yes Yes Ye...
result:
ok 525 token(s): yes count is 317, no count is 208
Test #8:
score: 0
Accepted
time: 0ms
memory: 5608kb
input:
3136 3 3 1 1 1 1 1 1 3 3 1 1 1 2 1 1 3 3 1 1 1 3 1 1 3 3 1 1 1 1 1 4 3 3 1 1 1 5 1 1 3 3 1 1 1 1 1 6 3 3 1 1 1 2 1 2 3 3 1 1 1 2 1 3 3 3 1 1 1 1 4 2 3 3 1 1 1 2 5 1 3 3 1 1 1 1 6 2 3 3 1 1 1 3 3 1 3 3 1 1 1 4 1 3 3 3 1 1 1 1 5 3 3 3 1 1 1 1 3 6 3 3 1 1 1 4 1 4 3 3 1 1 1 4 1 5 3 3 1 1 1 4 1 6 3 3 1 1...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes No No No No No No No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes...
result:
ok 3136 token(s): yes count is 1458, no count is 1678
Test #9:
score: 0
Accepted
time: 8ms
memory: 5624kb
input:
17640 3 4 1 1 1 1 1 1 1 3 4 1 1 1 2 1 1 1 3 4 1 1 1 1 1 1 3 3 4 1 1 1 1 1 1 4 3 4 1 1 1 5 1 1 1 3 4 1 1 1 1 6 1 1 3 4 1 1 1 7 1 1 1 3 4 1 1 1 1 1 2 2 3 4 1 1 1 1 2 3 1 3 4 1 1 1 1 4 1 2 3 4 1 1 1 5 1 2 1 3 4 1 1 1 2 1 1 6 3 4 1 1 1 7 1 1 2 3 4 1 1 1 3 3 1 1 3 4 1 1 1 4 1 3 1 3 4 1 1 1 1 1 3 5 3 4 1 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes No N...
result:
ok 17640 token(s): yes count is 6647, no count is 10993
Test #10:
score: 0
Accepted
time: 8ms
memory: 5612kb
input:
17640 4 3 1 1 1 1 1 1 1 4 3 1 1 1 1 1 2 1 4 3 1 1 1 1 3 1 1 4 3 1 1 1 1 1 1 4 4 3 1 1 1 1 1 5 1 4 3 1 1 1 1 6 1 1 4 3 1 1 1 1 1 1 7 4 3 1 1 1 1 1 2 2 4 3 1 1 1 1 3 1 2 4 3 1 1 1 1 2 4 1 4 3 1 1 1 1 1 2 5 4 3 1 1 1 1 1 2 6 4 3 1 1 1 1 7 2 1 4 3 1 1 1 1 1 3 3 4 3 1 1 1 1 4 1 3 4 3 1 1 1 1 5 3 1 4 3 1 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes No N...
result:
ok 17640 token(s): yes count is 8926, no count is 8714
Test #11:
score: 0
Accepted
time: 41ms
memory: 5844kb
input:
95040 3 5 1 1 1 1 1 1 1 1 3 5 1 1 1 2 1 1 1 1 3 5 1 1 1 1 3 1 1 1 3 5 1 1 1 1 1 4 1 1 3 5 1 1 1 1 5 1 1 1 3 5 1 1 1 1 1 6 1 1 3 5 1 1 1 7 1 1 1 1 3 5 1 1 1 1 1 1 8 1 3 5 1 1 1 2 1 2 1 1 3 5 1 1 1 1 1 2 1 3 3 5 1 1 1 1 4 2 1 1 3 5 1 1 1 2 5 1 1 1 3 5 1 1 1 6 1 2 1 1 3 5 1 1 1 1 7 2 1 1 3 5 1 1 1 1 8 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 95040 token(s): yes count is 29907, no count is 65133
Test #12:
score: -100
Wrong Answer
time: 45ms
memory: 5524kb
input:
95040 5 3 1 1 1 1 1 1 1 1 5 3 1 1 1 1 1 2 1 1 5 3 1 1 1 1 1 3 1 1 5 3 1 1 1 1 1 4 1 1 5 3 1 1 1 1 1 5 1 1 5 3 1 1 1 1 1 1 6 1 5 3 1 1 1 1 1 1 1 7 5 3 1 1 1 1 1 1 8 1 5 3 1 1 1 1 1 1 2 2 5 3 1 1 1 1 1 1 3 2 5 3 1 1 1 1 1 4 1 2 5 3 1 1 1 1 1 2 5 1 5 3 1 1 1 1 1 6 1 2 5 3 1 1 1 1 1 1 7 2 5 3 1 1 1 1 1 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
wrong answer expected NO, found YES [17153rd token]