QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#818879#9873. Last Chance: Threads of DespairicealsoheatWA 45ms5844kbC++175.9kb2024-12-18 10:27:442024-12-18 10:27:51

Judging History

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

  • [2024-12-18 10:27:51]
  • 评测
  • 测评结果:WA
  • 用时:45ms
  • 内存:5844kb
  • [2024-12-18 10:27:44]
  • 提交

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]