CSES - Putka Open 2025 – 2/5

Submission details
Task:	Ryhmät
Sender:	anton_h
Submission time:	2025-09-28 23:25:59 +0300
Language:	C++ (C++20)
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0
#2	WRONG ANSWER	0
#3	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	WRONG ANSWER	0.00 s	1, 2, 3	details
#2	WRONG ANSWER	0.00 s	1, 2, 3	details
#3	ACCEPTED	0.01 s	1, 2, 3	details
#4	ACCEPTED	0.00 s	1, 2, 3	details
#5	ACCEPTED	0.01 s	1, 2, 3	details
#6	ACCEPTED	0.03 s	2	details
#7	WRONG ANSWER	0.05 s	2	details
#8	ACCEPTED	0.18 s	2	details
#9	ACCEPTED	0.01 s	2, 3	details
#10	ACCEPTED	0.21 s	3	details
#11	WRONG ANSWER	0.10 s	3	details
#12	WRONG ANSWER	0.09 s	3	details
#13	ACCEPTED	0.10 s	3	details
#14	ACCEPTED	0.16 s	3	details
#15	WRONG ANSWER	0.23 s	3	details
#16	ACCEPTED	0.17 s	3	details

Code

#include <bits/stdc++.h>
using namespace std;

using ll=int;
using vl=vector<ll>;
#define all(c) begin(c),end(c)
#define pb push_back
#define sz(c) ll((c).size())

#define FOR(i,a,b) for(ll i=(a);i<(b);i++)

#define TR(x) ({ if(1) cout << __LINE__ << ": " #x " = " << (x) << endl; })

// Only when needed
using dd = double;
const dd eps = 1e-10;
using vd = vector<dd>;
using vvd = vector<vd>;

using vvl = vector<vl>;

struct BIT{
	ll n;
	vl bit;
	
	BIT(ll N) : n(N), bit(n+1) {}
	
	void update(ll i, ll v) { // a_i += v
		for(i++; i<=n; i+=i&-i) bit[i] += v;
	}
	
	ll query(ll i) { // a_0 + ... + a_i-1
		ll res = 0;
		for(; i; i-=i&-i) res += bit[i];
		return res;
	}
};

using pll = pair<ll, ll>;
int main(int argc, char const *argv[])
{
    ll n; cin >> n;
    ll t; cin >> t;
    vvl upd(n + 1);
    vl done_cnt(n + 2);
    FOR(i, 0, n){
        ll a, b;
        cin >> a >> b;
        upd[a].pb(b);
        done_cnt[b + 1]++;
    }
    FOR(i, 1, sz(done_cnt)){
        done_cnt[i] += done_cnt[i - 1];
    }

    struct query{
        int tc, a, b;
        //int end;
    };
    vector<vector<query>> qus(n + 1);
    vl ans(t, -1);

    vector<vvl> compr(t);
    vector<vector<pll>> t_pts(t);
    FOR(tc, 0, t){
        ll m, sum = 0;
        cin >> m;
        vl pts(m);
        for(ll &x : pts) {
            cin >> x;
            sum += x;
        }
        if(sum > n){
            ans[tc] = 0;
            continue;
        }
        sort(all(pts));

        vector<pll> pts2;
        for(ll &x : pts){
            if(pts2.empty() || x != pts2.back().first)
                pts2.emplace_back(x, 1);
            else pts2.back().second += 1;
        }
        t_pts[tc] = pts2;
        assert(sz(pts2) < 500);
        ll tn = sz(pts2);
        compr[tc].resize(tn, vl(tn));
        FOR(i, 0, tn){
            FOR(j, 0, tn){
                query q = {tc, i, j};
                // q.end = (j == tn - 1 ? n + 1 : pts2[j + 1].first);
                qus[pts2[i].first].pb(q);
            }
        }
    }
    BIT bit(n + 5);
    FOR(i, 1, n + 1){
        for(ll x : upd[i]) bit.update(x, 1);
        for(auto q : qus[i]){
            ll e2 = q.b == sz(t_pts[q.tc]) - 1 ? n + 1 : t_pts[q.tc][q.b + 1].first;
            // assert(e2 == q.end);
            compr[q.tc][q.a][q.b] = bit.query(e2);
        }
    }
    FOR(tc, 0, t){
        if(ans[tc] == 0) continue;
        ll tn = sz(compr[tc]);
        // FOR(i, 0, tn){
        //     for(ll j = tn - 1; j >= i + 1; j--)
        //         compr[tc][i][j] -= compr[tc][i][j - 1];
        //     compr[tc][i][i] -= done_cnt[t_pts[tc][i].first];
        // }
        // FOR(j, 0, tn){
        //     for(ll i = j; i >= 1; i--){
        //         compr[tc][i][j] -= compr[tc][i - 1][j];
        //     }
        // }
        for(ll i = tn - 1; i >= 0; i--){
            for(ll j = tn - 1; j >= 0; j--){
                if(i > 0) compr[tc][i][j] -= compr[tc][i - 1][j];
                if(j > 0) compr[tc][i][j] -= compr[tc][i][j - 1];
                if(i > 0 && j > 0) compr[tc][i][j] += compr[tc][i - 1][j - 1];
            }
        }
        vl cur(tn);
        FOR(i, 0, tn){
            FOR(j, i, tn) cur[j] += compr[tc][i][j];
            ll ms = t_pts[tc][i].first * t_pts[tc][i].second;
            FOR(j, i, tn){
                if(ms >= cur[j]){
                    ms -= cur[j];
                    cur[j] = 0;
                }else{
                    cur[j] -= ms;
                    ms = 0;
                    break;
                }
            }
            ans[tc] = ms == 0;
        }
    }

    FOR(tc, 0, t){
        cout << (ans[tc] ? "YES\n" : "NO\n");
    }

    return 0;
}

Test details

Test 1

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`100 100 10 10 10 10 6 9 6 8 ...` view save

correct output
`YES YES YES NO YES ...` view save

user output
`YES YES YES NO YES ...` view save

Test 2

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`100 100 9 9 6 10 8 10 8 8 ...` view save

correct output
`NO YES NO YES NO ...` view save

user output
`NO YES NO YES NO ...` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 100 1 1 1 1 1 1 1 1 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 100 100 100 100 100 100 100 100 100 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 100 4 9 3 8 7 9 7 9 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` view save

Test 6

Group: 2

Verdict: ACCEPTED

input
`1000 1000 9 10 2 5 10 10 5 5 ...` view save

correct output
`YES YES YES YES NO ...` view save

user output
`YES YES YES YES NO ...` view save

Test 7

Group: 2

Verdict: WRONG ANSWER

input
`1000 1000 5 7 9 9 3 7 8 10 ...` view save

correct output
`YES NO NO YES YES ...` view save

user output
`YES NO NO YES YES ...` view save

Test 8

Group: 2

Verdict: ACCEPTED

input
`1000 1000 1 1 1 1 1 1 1 1 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
`1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 10

Group: 3

Verdict: ACCEPTED

input
`100000 1000 774 778 363 852 309 668 261 459 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 11

Group: 3

Verdict: WRONG ANSWER

input
`100000 1000 1233 1914 901 3963 1277 4293 1083 1599 ...` view save

correct output
`NO NO YES NO NO ...` view save

user output
`NO NO YES NO NO ...` view save

Test 12

Group: 3

Verdict: WRONG ANSWER

input
`100000 1000 1970 8631 4606 5797 6317 8162 8204 8789 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` view save

Test 13

Group: 3

Verdict: ACCEPTED

input
`100000 1000 1000 1000 1000 1000 1000 1000 1000 1000 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 14

Group: 3

Verdict: ACCEPTED

input
`100000 100000 1 100000 1 100000 1 100000 1 100000 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 15

Group: 3

Verdict: WRONG ANSWER

input
`100000 100000 80971 98445 93046 96043 74840 94035 95931 96609 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` view save

Test 16

Group: 3

Verdict: ACCEPTED

input
`100000 10000 6481 14350 69129 87600 6217 16462 4387 16625 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Putka Open 2025 – 2/5

Ryhmät

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Tasks

Submissions (anton_h)