CSES - Putka Open 2025 – 1/5

Submission details
Task:	Järjestys
Sender:	jlaire
Submission time:	2025-09-07 02:00:33 +0300
Language:	C++ (C++17)
Status:	READY
Result:	10

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	TIME LIMIT EXCEEDED	0
#3	TIME LIMIT EXCEEDED	0
#4	TIME LIMIT EXCEEDED	0
#5	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.00 s	1, 4, 5	details
#2	ACCEPTED	0.00 s	1, 4, 5	details
#3	ACCEPTED	0.01 s	1, 4, 5	details
#4	ACCEPTED	0.01 s	1, 4, 5	details
#5	ACCEPTED	0.01 s	1, 4, 5	details
#6	ACCEPTED	0.01 s	1, 2, 4, 5	details
#7	ACCEPTED	0.01 s	1, 3, 4, 5	details
#8	ACCEPTED	0.01 s	1, 4, 5	details
#9	ACCEPTED	0.39 s	2, 4, 5	details
#10	ACCEPTED	0.87 s	3, 4, 5	details
#11	ACCEPTED	0.03 s	4, 5	details
#12	ACCEPTED	0.69 s	4, 5	details
#13	TIME LIMIT EXCEEDED	--	4, 5	details
#14	TIME LIMIT EXCEEDED	--	4, 5	details
#15	TIME LIMIT EXCEEDED	--	2, 5	details
#16	TIME LIMIT EXCEEDED	--	3, 5	details
#17	ACCEPTED	0.10 s	5	details
#18	TIME LIMIT EXCEEDED	--	5	details
#19	TIME LIMIT EXCEEDED	--	5	details
#20	TIME LIMIT EXCEEDED	--	5	details
#21	TIME LIMIT EXCEEDED	--	5	details
#22	TIME LIMIT EXCEEDED	--	5	details

Compiler report

input/code.cpp: In function 'ANS solve(const Viii&)':
input/code.cpp:347:57: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  347 |             if (R_OCC[R].size() == 1 && L_OCC[R].size() == nnn) {
      |                                         ~~~~~~~~~~~~~~~~^~~~~~
input/code.cpp:460:25: warning: comparison of integer expressions of different signedness: 'std::multiset<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  460 |         if (NOPS.size() == oldsz) return {};
      |             ~~~~~~~~~~~~^~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
using Viii = vector<iii>;
using ANS = optional<Viii>;

#define LEFT get<0>
#define RIGHT get<1>
#define ID get<2>
#define FAKE_ID_BEGIN (-1)
#define FAKE_ID_END (-2)

#define RL(x) ii((x).second, (x).first)

struct TEST {
    Viii V;
    multiset<iii> nops;
    Viii X;
};

Viii compressL(const Viii& V) {
    set<int> RR;
    for (auto [L,R,id] : V) {
        RR.insert(R);
    }
    map<int,int> newL;
    {
        int misses = 0;
        for (auto [L,R_,id_] : V) {
            auto it = RR.lower_bound(L);
            if (it==RR.end() || (*it>L && it==RR.begin())) {
                if (misses++) return {};
                newL[L] = 0;
                continue;
            }
            if (*it > L) --it;
            assert(*it <= L);
            newL[L] = *it;
        }
    }
    Viii X;
    for (auto [L,R,id] : V) {
        X.emplace_back(newL[L], R, id);
    }
    return X;
}

Viii compressR(const Viii& V) {
    set<int> LL;
    for (auto [L,R,id] : V) {
        LL.insert(L);
    }
    map<int,int> newR;
    {
        int misses = 0;
        for (auto [L_,R,id_] : V) {
            auto it = LL.lower_bound(R);
            if (it==LL.end()) {
                if (misses++) return {};
                newR[R] = 1e9+1;
                continue;
            }
            assert(*it >= R);
            newR[R] = *it;
        }
    }
    Viii X;
    for (auto [L,R,id] : V) {
        X.emplace_back(L, newR[R], id);
    }
    return X;
}

Viii remove_nops(TEST& T, const Viii& V) {
    Viii X;
    for (auto [L,R,id] : V) {
        if (id >= 0 && L == R) {
            T.nops.insert(V[id]);
            continue;
        }
        X.emplace_back(L, R, id);
    }
    return X;
}

Viii compress_coord(const Viii& V) {
    set<int> S;
    for (auto [L,R,id] : V) {
        S.insert(L);
        S.insert(R);
    }
    map<int,int> M;
    int next = 0;
    for (int x : S) M[x] = next++;
    Viii X;
    for (auto [L,R,id] : V) {
        X.emplace_back(M[L], M[R], id);
    }
    return X;
}

bool compress(TEST& T) {
    Viii V2 = compressL(T.V);
    if (V2.empty()) return false;
    Viii V3 = compressR(V2);
    if (V3.empty()) return false;
    Viii V4 = remove_nops(T, V3);
    Viii V5 = compress_coord(V4);
    Viii V6 = compressL(V5);
    Viii V7 = compressR(V6);
    T.X = move(V7);
    return true;
}

TEST preprocess(const Viii& V0) {
    TEST T;
    Viii& V = T.V;
    V = V0;
    V.emplace_back(0, 0, FAKE_ID_BEGIN);
    V.emplace_back(1e9+1, 1e9+1, FAKE_ID_END);
    if (!compress(T)) {
        T.V.clear();
    }
    return T;
}

ANS postprocess(TEST& T, const ANS& ans) {
    if (!ans) return {};
    Viii res;
    assert(ID(*ans->begin()) == FAKE_ID_BEGIN);
    assert(ID(*ans->rbegin()) == FAKE_ID_END);
    const Viii& V = T.V;
    multiset<iii> &nops = T.nops;
    for (int i=1; i<(int)ans->size(); i++) {
        int prev_id = ID((*ans)[i-1]);
        int id = ID((*ans)[i]);
        int PREV = prev_id == FAKE_ID_BEGIN ? 0 : RIGHT(V[prev_id]);
        int NEXT = id == FAKE_ID_END ? 1e9 : LEFT(V[id]);
        for (auto it = nops.begin(); it != nops.end();) {
            int L = LEFT(*it);
            int R = RIGHT(*it);
            if (L >= PREV && R <= NEXT) {
                res.push_back(T.V[ID(*it)]);
                PREV = RIGHT(*it);
                it = nops.erase(it);
            }
            else {
                it++;
            }
        }
        if (id >= 0) res.push_back(V[id]);
    }
    if (!nops.empty()) return {};
    return res;
}

bool ok(const multiset<int>& LS, const multiset<int>& RS) {
    set<int> S;
    for (int x:LS) S.insert(x);
    for (int x:RS) S.insert(x);
    int L_below = 0;
    int R_below = 0;
    auto Lit = LS.begin();
    auto Rit = RS.begin();
    for (int x : S) {
        for (; Lit != LS.end() && *Lit <= x; Lit++, L_below++);
        for (; Rit != RS.end() && *Rit <= x; Rit++, R_below++);
        if (L_below > R_below) return false;
        int L_above = LS.size() - L_below;
        int R_above = RS.size() - R_below;
        if (R_above > L_above) return false;
    }
    return true;
}

ANS solve(const Viii& V) {
    if (V.empty()) return {};
    map<int,iii> VM;
    for (auto x : V) VM[ID(x)] = x;
    int n = V.size();
    map<int,int> Lid, Rid;
    map<ii,set<ii>> Ladj, Radj;
    map<int,int> Lmost, Rmost;

    map<ii,int> ALIVE;
    map<ii,vector<int>> BACKLOG;

    multiset<iii> NOPS;
    map<int,set<int>> L_OCC, R_OCC;

    auto hasL = [&](int id) { return Lid.count(id); };
    auto hasR = [&](int id) { return Rid.count(id); };

    std::function<int(int)> get_Lmost;
    get_Lmost = [&](int id) {
        if (!hasL(id)) return id;
        if (!Lmost.count(id)) Lmost[id] = Lid[id];
        return Lmost[id] = get_Lmost(Lmost[id]);
    };
    std::function<int(int)> get_Rmost;
    get_Rmost = [&](int id) {
        if (!hasR(id)) return id;
        if (!Rmost.count(id)) Rmost[id] = Rid[id];
        return Rmost[id] = get_Rmost(Rmost[id]);
    };

    auto kill = [&](int L, int R) {
        ii LR(L,R);
        int id = ALIVE[LR];
        R_OCC[R].erase(id);
        L_OCC[L].erase(id);
        if (!BACKLOG.count(LR)) {
            ALIVE.erase(LR);
            Ladj.erase(LR);
            Radj.erase(LR);
            for (auto& p : Ladj) p.second.erase(RL(LR));
            for (auto& p : Radj) p.second.erase(LR);
        }
        else {
            assert(!BACKLOG[LR].empty());
            int id2 = BACKLOG[LR].back();
            BACKLOG[LR].pop_back();
            ALIVE[LR] = id2;
            if (BACKLOG[LR].empty()) {
                BACKLOG.erase(LR);
            }
        }
    };

    auto is_fixed_begin = [&](int id) { return get_Lmost(id) == FAKE_ID_BEGIN; };
    auto is_fixed_end = [&](int id) { return get_Rmost(id) == FAKE_ID_END; };

    int TODO = n - 1;
    auto spawn = [&](int L, int R, int id) {
        if (L == R && id>=0) {
            id = get_Lmost(id);
            NOPS.emplace(L,R,id);
            TODO--;
            return;
        }
        if (!is_fixed_begin(id)) L_OCC[L].insert(id);
        if (!is_fixed_end(id)) R_OCC[R].insert(id);
        ii LR(L,R);
        if (ALIVE.count(LR)) {
            BACKLOG[LR].push_back(id);
            return;
        }
        for (auto [LR2,id2] : ALIVE) {
            auto [L2,R2] = LR2;
            if (L >= R2) {
                Ladj[LR].insert(RL(LR2));
                Radj[LR2].insert(LR);
            }
            if (L2 >= R) {
                Ladj[LR2].insert(RL(LR));
                Radj[LR].insert(LR2);
            }
        }
        ALIVE[LR] = id;
    };

    for (auto [L,R,id] : V) spawn(L,R,id);

    auto getLR = [&](int id) {
        int L = get_Lmost(id);
        int R = get_Rmost(id);
        return ii(LEFT(VM[L]), RIGHT(VM[R]));
    };

    auto join = [&](int L, int R) {
        TODO--;
        L = get_Rmost(L);
        R = get_Lmost(R);
        ii Lii = getLR(L);
        ii Rii = getLR(R);
        R_OCC[Lii.second].erase(L);
        L_OCC[Rii.first].erase(R);
        assert(Ladj[Rii].count(RL(Lii)));
        assert(Radj[Lii].count(Rii));
        assert(!Lid.count(R));
        assert(!Rid.count(L));
        Rid[L] = R;
        Lid[R] = L;
        Rmost[L] = get_Rmost(R);
        Lmost[R] = get_Lmost(L);
        kill(Lii.first, Lii.second);
        kill(Rii.first, Rii.second);
        spawn(Lii.first, Rii.second, L);
        if (is_fixed_begin(L) && TODO>1) {
            ii newLR(Lii.first, Rii.second);
            for (ii LR2 : set<ii>(Radj[newLR])) {
                if (is_fixed_end(ALIVE[LR2])) {
                    Radj[newLR].erase(LR2);
                    Ladj[LR2].erase(RL(newLR));
                }
            }
        }
        if (is_fixed_end(R) && TODO>1) {
            ii newLR(Lii.first, Rii.second);
            for (ii RL2 : set<ii>(Ladj[newLR])) {
                if (is_fixed_begin(ALIVE[RL(RL2)])) {
                    Ladj[newLR].erase(RL2);
                    Radj[RL(RL2)].erase(newLR);
                }
            }
        }
    };
    while (TODO > 0) {
        if (Ladj.empty()) return {};
        if (Radj.empty()) return {};
        if (TODO == 1) {
            assert(ALIVE.size() == 2);
            for (auto [LR,id] : ALIVE) {
                for (auto [LR2,id2] : ALIVE) if (id != id2) {
                    if (LR.second <= LR2.first) {
                        Ladj[LR2].insert(RL(LR));
                        Radj[LR].insert(LR2);
                        join(id, id2);
                        goto next;
                    }
                }
            }
        }
        for (const auto& [LR,S] : Ladj) {
            if (is_fixed_begin(ALIVE[LR])) continue;
            if (S.empty()) return {};
            if (S.size() == 1) {
                ii LR2 = RL(*S.begin());
                join(ALIVE[LR2], ALIVE[LR]);
                goto next;
            }
        }
        for (const auto& [LR,S] : Radj) {
            if (is_fixed_end(ALIVE[LR])) continue;
            if (S.empty()) return {};
            if (S.size() == 1) {
                ii LR2 = *S.begin();
                join(ALIVE[LR], ALIVE[LR2]);
                goto next;
            }
        }
        for (auto [LR,id] : ALIVE) {
            auto [L,R] = LR;
            int nnn = 1 + (L==R);
            if (R_OCC[R].size() == 1 && L_OCC[R].size() == nnn) {
                const auto& S = Radj[LR];
                join(id, ALIVE[*S.begin()]);
                goto next;
            }
        }
        {
            map<int,int> L_OCC, R_OCC;
            for (auto [LR,id] : ALIVE) {
                auto [L,R] = LR;
                if (!is_fixed_begin(id)) L_OCC[L]++;
                if (!is_fixed_end(id)) R_OCC[R]++;
            }
            for (auto [LR,id] : ALIVE) {
                auto [L,R] = LR;
                int nnn = 1 + (L==R);
                if (R_OCC[R] == 1 && L_OCC[R] == nnn) {
                    const auto& S = Radj[LR];
                    join(id, ALIVE[*S.begin()]);
                    goto next;
                }
            }
        }
        {
            multiset<int> LS, RS;
            for (auto [L,R,id] : V) {
                if (id != FAKE_ID_BEGIN && !hasL(id)) LS.insert(L);
                if (id != FAKE_ID_END && !hasR(id)) RS.insert(R);
            }
            for (auto [LR,id] : ALIVE) {
                if (is_fixed_begin(id)) continue;
                if (is_fixed_end(id)) continue;
                int first = RIGHT(getLR(FAKE_ID_BEGIN));
                auto [L,R] = LR;
                if (L < first) continue;
                LS.erase(LS.find(L));
                RS.erase(RS.find(first));
                if (!ok(LS,RS)) {
                    LS.insert(L);
                    RS.insert(first);
                    continue;
                }
                join(FAKE_ID_BEGIN, id);
                goto next;
            }
        }
        //return {};
        for (const auto& [LR,S] : Ladj) {
            if (is_fixed_begin(ALIVE[LR])) continue;
            assert(S.size() >= 2);
            auto it = S.rbegin();
            auto it2 = next(it);
            if (it->first != it2->first) {
                join(ALIVE[RL(*it)], ALIVE[LR]);
                goto next;
            }
        }
        for (const auto& [LR,S] : Radj) {
            if (is_fixed_end(ALIVE[LR])) continue;
            assert(S.size() >= 2);
            auto it = S.begin();
            auto it2 = next(it);
            if (it->first != it2->first) {
                join(ALIVE[LR], ALIVE[*it]);
                goto next;
            }
        }
        for (const auto& [LR,S] : Radj) {
            if (is_fixed_end(ALIVE[LR])) continue;
            assert(S.size() >= 2);
            auto it = S.begin();
            if (it->first == LR.second) {
                join(ALIVE[LR], ALIVE[*it]);
                goto next;
            }
        }
        return {};
next:;
    }

    Viii ans;
    for (int id = FAKE_ID_BEGIN;; id = Rid[id]) {
        ans.push_back(VM[id]);
        if (id == FAKE_ID_END) break;
    }
    while (!NOPS.empty()) {
        int oldsz = NOPS.size();
        Viii res;
        res.push_back(ans[0]);
        for (int i=1; i<(int)ans.size(); i++) {
            int prev_id = ID(ans[i-1]);
            int id = ID(ans[i]);
            int PREV = prev_id == FAKE_ID_BEGIN ? 0 : RIGHT(VM[prev_id]);
            int NEXT = id == FAKE_ID_END ? 1e9 : LEFT(VM[id]);
            for (auto it = NOPS.begin(); it != NOPS.end();) {
                int L = LEFT(*it);
                int R = RIGHT(*it);
                if (L >= PREV && R <= NEXT) {
                    int xx = ID(*it);
                    for (;;) {
                        res.push_back(VM[xx]);
                        if (!Rid.count(xx)) break;
                        xx = Rid[xx];
                    }
                    it = NOPS.erase(it);
                }
                else {
                    it++;
                }
            }
            res.push_back(VM[id]);
        }
        swap(ans, res);
        if (NOPS.size() == oldsz) return {};
    }
    return ans;
}

ANS solve2(const Viii& V) {
    TEST T = preprocess(V);
    auto ans = solve(T.X);
    if (ans) {
        return postprocess(T, *ans);
    }
    return {};
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t; cin>>t;
    while (t--) {
        int n; cin>>n;
        set<iii> S;
        vector<iii> V;
        for (int i=0; i<n; i++) {
            int x,y; cin>>x>>y;
            S.emplace(x,y,i);
            V.emplace_back(x,y,i);
        }
        if (n==1) {
            cout << "YES\n";
            cout << LEFT(V[0]) << ' ' << RIGHT(V[0]) << '\n';
            continue;
        }
        if (ANS ans = solve2(V)) {
            cout << "YES\n";
            for (auto [x,y,_] : *ans) {
                cout << x << ' ' << y << '\n';
            }
        }
        else cout << "NO\n";
    }
}

Test details

Test 1

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 1 74 75 1 100 43 ...` view save

correct output
`YES 74 75 YES 100 43 YES ...` view save

user output
`YES 74 75 YES 100 43 YES ...` Truncated

Test 2

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 2 80 54 51 61 2 ...` view save

correct output
`YES 51 61 80 54 YES 2 64 ...` view save

user output
`YES 51 61 80 54 YES 2 64 ...` Truncated

Test 3

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 3 3 74 91 45 100 24 ...` view save

correct output
`YES 3 74 100 24 91 45 YES ...` view save

user output
`YES 3 74 91 45 100 24 YES ...` Truncated

Test 4

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 4 88 50 62 41 12 86 ...` view save

correct output
`YES 12 86 88 50 62 41 66 93 ...` view save

user output
`YES 12 86 88 50 62 41 66 93 ...` Truncated

Test 5

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 5 82 80 80 92 5 22 ...` view save

correct output
`YES 5 22 94 13 82 80 80 92 ...` view save

user output
`YES 5 22 82 80 80 92 93 91 ...` Truncated

Test 6

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
`100 5 34 38 26 30 1 6 ...` view save

correct output
`YES 1 6 12 22 26 30 34 38 ...` view save

user output
`YES 1 6 12 22 26 30 34 38 ...` Truncated

Test 7

Group: 1, 3, 4, 5

Verdict: ACCEPTED

input
`100 5 50 40 28 25 51 7 ...` view save

correct output
`YES 51 7 50 40 47 1 17 11 ...` view save

user output
`YES 17 11 28 25 50 40 51 7 ...` Truncated

Test 8

Group: 1, 4, 5

Verdict: ACCEPTED

input
`100 5 2 2 2 1 1 1 ...` view save

correct output
`YES 1 2 2 1 2 1 1 1 ...` view save

user output
`YES 1 1 1 2 2 2 2 1 ...` Truncated

Test 9

Group: 2, 4, 5

Verdict: ACCEPTED

input
`100 100 175870020 296379324 248160539 883842002 21934885 781732852 ...` view save

correct output
`NO YES 4976156 6890135 10553287 11923223 14617057 17728163 ...` view save

user output
`NO YES 4976156 6890135 10553287 11923223 14617057 17728163 ...` Truncated

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

input
`100 100 447597377 314433951 700232436 691277009 937268439 708165426 ...` view save

correct output
`YES 998963839 391778929 995772196 257222033 995754704 553123757 994629465 247775824 ...` view save

user output
`YES 80804061 58329306 78989197 22224979 86698875 65763632 131739372 728604 ...` Truncated

Test 11

Group: 4, 5

Verdict: ACCEPTED

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

correct output
`YES 1 2 2 1 1 2 2 2 ...` view save

user output
`YES 1 1 1 1 1 1 1 1 ...` Truncated

Test 12

Group: 4, 5

Verdict: ACCEPTED

input
`100 100 7 1 6 3 10 9 ...` view save

correct output
`YES 6 7 7 8 9 10 10 10 ...` view save

user output
`YES 1 9 9 9 9 9 9 2 ...` Truncated

Test 13

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

input
`100 100 51 5 85 77 91 84 ...` view save

correct output
`YES 100 24 100 25 100 3 100 6 ...` view save

user output
(empty)

Test 14

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

input
`100 100 823828194 863717310 593641073 340054211 420481158 965069109 ...` view save

correct output
`YES 999289319 634855378 996775156 433726648 983657502 55234695 981890636 112877413 ...` view save

user output
(empty)

Test 15

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

input
`100 500 88724450 89315226 266915464 267648621 189301651 189661541 ...` view save

correct output
`YES 764920 1459946 1936195 2832987 3691481 4085931 4991808 5840928 ...` view save

user output
(empty)

Test 16

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

input
`100 500 763682761 317584504 756010800 260162861 435911339 78070399 ...` view save

correct output
`YES 998768285 3307355 998714926 628486754 997115613 820932481 993320616 554600893 ...` view save

user output
(empty)

Test 17

Group: 5

Verdict: ACCEPTED

input
`100 500 2 2 2 1 1 2 ...` view save

correct output
`YES 1 2 2 2 2 1 1 2 ...` view save

user output
`YES 1 1 1 1 1 1 1 1 ...` Truncated

Test 18

Group: 5

Verdict: TIME LIMIT EXCEEDED

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

correct output
`YES 2 3 3 4 4 5 5 6 ...` view save

user output
(empty)

Test 19

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100 500 85 87 89 70 70 92 ...` view save

correct output
`YES 96 97 100 67 100 10 100 97 ...` view save

user output
(empty)

Test 20

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100 500 861154169 119512584 569086662 606567153 288230434 322196278 ...` view save

correct output
`YES 999945324 969534372 999738857 240617694 999244114 722161553 999207839 557351400 ...` view save

user output
(empty)

Test 21

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100 500 116439250 401518028 280329609 193466222 674040956 209050570 ...` view save

correct output
`NO YES 773701149 773852119 987509190 315670966 977413249 510418200 ...` view save

user output
(empty)

Test 22

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
`100 500 934181189 942499518 684836806 395802802 957884803 570946201 ...` view save

correct output
`YES 999772640 505132174 999111650 140844643 999028633 888134186 999020109 291046771 ...` view save

user output
(empty)

Putka Open 2025 – 1/5

Järjestys

Compiler report

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

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Tasks

Submissions (jlaire)