QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#429195#6526. Canvasdnialh#RE 358ms56440kbC++207.1kb2024-06-02 02:57:392024-06-02 02:57:40

Judging History

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

  • [2024-06-02 02:57:40]
  • 评测
  • 测评结果:RE
  • 用时:358ms
  • 内存:56440kb
  • [2024-06-02 02:57:39]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define F0R(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i <= b; i++)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define FORd(i,a,b) for (int i = (b); i >= (a); i--)
#define trav(a, x) for (auto& a : x)
#define rep(i, a, b) for(int i = a; i < (b); ++i)

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

const char nl = '\n';
const int MAX_N = 100011;
const ll INF = (1<<29) + 123;
const ll MOD = 1000000007; // 998244353
const ld PI = 4*atan((ld)1);

template <typename T> bool ckmin(T& a, const T& b) { return a > b ? a=b, 1 : 0; }
template <typename T> bool ckmax(T& a, const T& b) { return b > a ? a=b, 1 : 0; }

/**** Credit to chatgpt 4.0 ****/

// Stream operator for std::pair
template<typename T1, typename T2>
ostream& operator<<(ostream &out, const pair<T1, T2> &v) {
    out << "(" << v.first << ", " << v.second << ")"; 
    return out;
}

// Trait to check if a type is iterable
template<typename T, typename = void>
struct is_iterable : false_type {};

template<typename T>
struct is_iterable<T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>> : true_type {};

// Stream operator for iterable types excluding std::string
template<typename TT>
typename enable_if<is_iterable<TT>::value && !is_same<TT, string>::value, ostream&>::type
operator<<(ostream& out, const TT& c) {
    out << "{ ";
    for (const auto& x : c) out << x << " ";
    out << "}"; 
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, std::stack<T> container) {
    std::vector<T> elements;
    while (!container.empty()) {
        elements.push_back(container.top());
        container.pop();
    }
    std::reverse(elements.begin(), elements.end()); // Reverse to maintain order
    return out << elements;
}

template<typename T>
ostream& operator<<(ostream& out, std::queue<T> container) {
    std::vector<T> elements;
    while (!container.empty()) {
        elements.push_back(container.front());
        container.pop();
    }
    return out << elements;
}

// Helper function to print std::priority_queue
template<typename T, typename Container, typename Compare>
ostream& operator<<(ostream& out, std::priority_queue<T, Container, Compare> pq) {
    out << "{";
    while (!pq.empty()) {
        out << " " << pq.top();
        pq.pop();
    }
    out << " }";
    return out;
}

#ifdef DBG
void dbg_out() { cerr << endl; }

template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
}

#define dbg(...) cerr << #__VA_ARGS__ << ":", dbg_out(__VA_ARGS__);
#define dbg_array(a, n) cerr << #a << ": { "; for(int i = 0; i < n; i++) cerr << a[i] << " "; cerr << "}\n";
#else
#define dbg(...)
#define dbg_array(a, n)
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MX = 3e5+5;

bool vis[MX];
bool sources[MX];

vi val, comp, z, cont;
int Time, ncomps;
int n, m;
template<class G, class F> int dfs(int j, G& g, F& f) {
	int low = val[j] = ++Time, x; z.push_back(j);
	for (auto e : g[j]) if (comp[e.f] < 0)
		low = min(low, val[e.f] ?: dfs(e.f,g,f));

	if (low == val[j]) {
		do {
			x = z.back(); z.pop_back();
			comp[x] = ncomps;
			cont.push_back(x);
		} while (x != j);
		f(cont); cont.clear();
		ncomps++;
	}
	return val[j] = low;
}
template<class G, class F> void scc(G& g, F f) {
	val.assign(n, 0); comp.assign(n, -1);
	Time = ncomps = 0;
    z.clear();
    cont.clear();
	rep(i,0,n) if (comp[i] < 0) dfs(i, g, f);
}

vpi gr[MX], rgr[MX]; // graph and reverse graph

bool seen[MX];
vi cur;
void dfs2(int v) {
    if (seen[v]) return;
    seen[v] = 1;
    trav(e, gr[v]) {
        cur.pb(e.s);
        dfs2(e.f);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) {
        cin >> n >> m;
        F0R(i, n) vis[i] = 0;
        F0R(i, n) sources[i] = 0; 
        F0R(i, n) seen[i] = 0;
        F0R(i, n) gr[i].clear();
        F0R(i, n) rgr[i].clear();
        vi start, end;
        vector<array<int, 4>> ops;
        F0R(i, m) {
            int l, x, r, y; cin >> l >> x >> r >> y;
            l--; x--; r--; y--;
            ops.pb({l, x, r, y});
            if (x&&y) {
                end.pb(i);
                sources[l] = sources[r] = 1;
            } else if (x&&!y) {
                gr[r].pb({l, i});
                rgr[l].pb({r, i});
            } else if (!x&&y) {
                gr[l].pb({r, i});
                rgr[r].pb({l, i});
            } else {
                start.pb(i);
            }
            vis[l] = vis[r] = 1;
        }
        int ans = 0;
        F0R(i, n) if (vis[i]) ans+=2;
        scc(gr, [&](vi& v) {
            assert(sz(v));
            if (sz(v) == 1 && !vis[v[0]]) {
                return;
            }
            dbg("size", sz(v), "comp label", comp[v[0]]);
            dbg("comp", cont);
            // check if there's any sources in this component or if it has any parents
            bool ok = 0;
            trav(u, v) {
                trav(e, rgr[u]) {
                    if (comp[e.f] != comp[u]) {
                        dbg(e.f);
                        ok = 1;
                    }
                }
                if (sources[u]) {
                    dbg(u, sz(rgr[u]), sources[u]);
                    ok = 1;
                    break;
                }
            }
            dbg(ok);
            if (!ok) {
                ans--;
                // pick someone random to be a source here
                sources[v[0]] = 1;
                dbg("new source", v[0]);
            }
        });
        cout << ans << nl;
        // now we just compute the ordering by dfs-ing from every source and reversing the vector
        vi order = start;
        F0R(i, n) {
            if (seen[i] || !sources[i]) continue;
            cur.clear();
            dfs2(i);
            dbg(i, cur);
            reverse(all(cur));
            order.insert(order.end(), cur.begin(), cur.end());
        }
        order.insert(order.end(), end.begin(), end.end());
        trav(o, order) cout << o+1 << " "; cout << nl;
        vi order_copy = order;
        sort(all(order_copy));
        vi V(m); iota(all(V), 0);
        if (V != order_copy) {
            while (1);
        }
        // check this ordering now
        int mark[n]; F0R(i, n) mark[i] = 0;
        trav(o, order) {
            auto cur = ops[o];
            mark[cur[0]] = cur[1]+1;
            mark[cur[2]] = cur[3]+1;
        }
        int ans2 = 0;
        F0R(i, n) ans2 += mark[i];
        dbg(ans, ans2);
        assert(ans == ans2);
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3872kb

input:

2
4 4
1 1 2 2
3 2 4 1
1 2 3 2
2 1 4 1
4 2
3 2 4 1
1 2 3 1

output:

7
4 1 2 3 
5
2 1 

result:

ok Correct. (2 test cases)

Test #2:

score: 0
Accepted
time: 2ms
memory: 5908kb

input:

1
10 13
1 1 2 2
2 1 3 2
1 2 3 1
3 1 4 2
4 1 5 2
5 1 6 2
4 2 6 1
7 1 8 2
8 1 9 2
7 2 9 1
5 2 9 1
8 2 10 2
1 1 10 1

output:

19
13 7 6 5 4 2 1 3 11 8 10 9 12 

result:

ok Correct. (1 test case)

Test #3:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

1
7 5
2 1 6 2
1 2 6 1
1 1 5 1
2 2 7 1
1 1 7 2

output:

8
3 1 4 5 2 

result:

ok Correct. (1 test case)

Test #4:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

1
7 6
2 1 7 2
2 1 4 2
1 2 4 1
2 1 6 1
1 1 6 2
2 2 6 1

output:

9
4 2 1 6 5 3 

result:

ok Correct. (1 test case)

Test #5:

score: 0
Accepted
time: 1ms
memory: 3676kb

input:

1
7 5
5 2 7 1
5 1 6 2
3 2 7 1
3 2 6 1
6 1 7 2

output:

7
3 5 4 2 1 

result:

ok Correct. (1 test case)

Test #6:

score: 0
Accepted
time: 1ms
memory: 5684kb

input:

1
7 6
1 2 5 1
2 1 7 2
1 2 7 1
2 2 7 1
1 1 5 2
1 2 3 1

output:

8
1 5 6 2 4 3 

result:

ok Correct. (1 test case)

Test #7:

score: 0
Accepted
time: 8ms
memory: 3748kb

input:

2000
15 16
2 2 3 1
12 2 15 1
3 2 9 1
6 2 14 1
2 1 15 2
5 2 6 1
7 1 10 1
9 2 15 1
2 2 3 1
4 2 12 1
2 2 9 1
5 2 8 2
3 2 13 1
12 1 13 2
9 2 13 1
5 1 14 2
15 15
5 2 11 1
1 2 8 1
8 1 15 2
6 2 8 2
8 2 9 1
1 1 6 2
6 1 9 2
2 2 5 1
2 1 10 2
7 2 10 1
1 1 15 2
5 2 15 1
7 1 11 2
1 1 2 1
5 2 9 1
15 14
3 1 5 2
1 ...

output:

23
7 6 4 16 11 9 8 15 13 14 10 2 5 1 3 12 
20
14 15 3 1 13 10 9 8 12 11 6 2 5 7 4 
21
2 11 13 6 10 3 9 12 7 14 8 4 1 5 
18
7 13 4 8 12 6 10 14 1 5 11 9 3 2 
21
6 5 17 8 4 18 19 10 7 2 13 3 11 14 16 9 12 1 15 
21
3 11 7 12 13 8 9 14 5 4 10 6 2 1 
21
3 14 8 1 5 2 11 9 7 15 6 13 4 12 10 
19
11 7 10 14 ...

result:

ok Correct. (2000 test cases)

Test #8:

score: 0
Accepted
time: 7ms
memory: 5780kb

input:

2000
15 18
10 1 15 2
10 1 15 2
3 2 13 1
5 1 6 2
2 1 10 2
3 2 5 2
7 1 12 2
2 2 3 1
12 1 13 2
5 2 11 1
7 1 15 2
5 1 15 2
6 1 11 2
2 1 6 1
5 1 10 2
5 2 10 1
2 1 7 2
2 1 15 2
15 17
7 2 15 1
6 2 10 1
3 2 12 1
13 2 14 1
1 1 7 2
6 2 15 1
6 2 13 2
1 2 6 1
10 2 15 1
12 2 15 1
9 1 10 2
13 1 15 2
9 2 12 1
3 1 ...

output:

20
14 18 11 3 9 7 17 15 12 10 13 4 16 2 1 5 8 6 
21
17 2 11 15 5 8 16 13 4 14 3 10 9 6 1 12 7 
21
1 13 11 8 16 15 6 3 5 4 2 17 12 9 18 7 10 14 
19
12 16 18 13 4 2 15 11 14 6 7 8 1 10 5 3 9 17 
19
4 3 15 13 11 1 5 2 14 16 7 12 10 8 9 6 
21
9 7 8 13 5 4 10 11 6 12 1 3 2 
20
6 12 9 1 10 3 13 4 11 7 8 2...

result:

ok Correct. (2000 test cases)

Test #9:

score: 0
Accepted
time: 1ms
memory: 5660kb

input:

5
27 33
18 2 23 1
13 1 23 2
2 1 7 2
4 2 7 1
2 1 4 2
9 1 27 2
26 2 27 1
3 2 11 1
2 1 4 2
12 1 18 2
4 2 7 1
25 2 26 1
12 1 17 2
5 1 27 2
5 2 22 1
13 2 25 1
2 1 4 2
4 2 7 1
2 2 26 1
4 2 7 1
2 2 7 1
2 2 17 1
19 1 26 1
3 2 24 1
11 1 24 2
3 2 24 1
3 1 9 2
18 1 22 2
9 1 11 2
5 2 23 2
12 2 17 1
2 2 7 1
4 2 ...

output:

33
23 17 9 5 32 21 20 18 11 4 3 19 33 15 28 1 2 16 12 7 14 13 10 31 22 26 25 8 29 6 27 24 30 
37
22 7 28 1 18 25 11 15 23 26 17 20 2 16 10 8 24 19 5 21 6 4 3 27 14 13 9 12 
38
22 3 23 6 14 11 29 7 25 35 31 20 12 34 33 24 21 16 5 2 1 36 27 30 28 15 10 26 4 9 13 19 18 8 32 17 
34
32 21 19 24 25 28 3 2...

result:

ok Correct. (5 test cases)

Test #10:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

5
27 37
10 2 25 2
18 2 22 1
18 1 22 2
2 1 24 2
14 2 26 1
4 1 27 2
15 2 25 1
24 1 27 2
7 2 20 1
11 1 18 1
2 1 14 2
15 1 25 2
10 2 15 1
9 1 16 2
24 2 27 1
24 1 27 2
10 2 12 1
10 1 15 2
9 2 14 1
6 1 15 2
7 1 27 2
24 1 27 2
6 1 22 2
16 1 20 2
15 1 24 2
4 1 27 2
24 1 27 2
2 1 4 2
24 2 27 1
7 1 26 2
24 1 ...

output:

35
10 28 23 34 25 18 13 7 12 20 36 3 2 33 5 30 21 9 24 14 19 11 4 37 35 26 29 32 31 27 22 16 8 15 6 17 1 
37
31 27 17 13 12 29 28 26 8 7 21 20 16 4 34 33 9 22 23 32 19 11 18 3 25 14 6 15 2 24 10 30 5 1 
35
22 21 1 24 26 14 6 4 2 30 18 8 3 31 23 20 34 25 33 10 5 15 32 7 16 29 17 11 27 19 13 12 9 28 
...

result:

ok Correct. (5 test cases)

Test #11:

score: 0
Accepted
time: 96ms
memory: 4596kb

input:

200
739 1933
110 1 669 2
17 2 403 1
39 1 538 2
36 2 267 1
66 2 259 1
55 2 483 1
245 2 450 1
30 1 729 2
318 1 568 2
344 1 681 2
11 2 37 1
15 2 192 1
55 2 344 1
426 2 596 1
3 2 683 1
499 1 614 1
302 1 367 2
220 1 528 1
223 2 563 1
255 2 719 1
153 2 688 1
371 2 648 1
704 2 715 1
367 2 477 1
451 2 698 2...

output:

1031
16 18 131 172 187 212 295 340 391 397 426 428 430 434 440 555 563 602 618 620 675 694 803 833 837 931 935 954 978 1005 1051 1127 1128 1243 1280 1363 1367 1406 1484 1535 1578 1583 1620 1632 1672 1724 1726 1757 1806 1924 1706 1344 946 855 779 402 1377 1887 1790 1522 1249 1215 1119 1091 524 927 15...

result:

ok Correct. (200 test cases)

Test #12:

score: 0
Accepted
time: 94ms
memory: 6668kb

input:

200
748 1673
173 2 219 1
77 1 143 2
19 2 384 1
277 2 371 1
272 2 424 1
203 2 737 1
90 1 129 2
302 1 717 2
527 2 700 1
124 2 673 1
129 2 708 1
546 2 650 1
151 2 689 1
475 2 603 1
173 1 574 2
277 1 605 2
129 2 499 1
373 2 546 1
52 2 66 1
238 1 618 2
373 2 473 1
154 2 244 1
278 1 618 2
112 1 129 2
361 ...

output:

1066
79 146 214 244 255 267 301 386 395 436 439 443 478 486 496 529 530 543 579 589 656 679 684 756 758 791 817 821 855 920 928 945 952 958 963 970 998 1000 1106 1262 1303 1366 1373 1377 1439 1496 1518 1586 1654 1673 1115 286 779 1217 954 1561 1316 1364 1324 1354 690 1452 1645 1558 1500 332 1090 867...

result:

ok Correct. (200 test cases)

Test #13:

score: 0
Accepted
time: 88ms
memory: 4680kb

input:

200
736 1822
500 2 641 1
91 1 700 2
525 2 576 1
101 2 364 1
304 1 689 2
12 2 636 1
338 2 358 1
15 2 296 1
12 2 123 1
608 1 666 2
135 2 473 1
361 1 667 2
137 2 348 1
381 1 502 2
107 1 277 2
23 1 137 2
262 1 602 2
493 1 573 2
158 2 306 1
137 1 587 2
238 2 682 1
580 2 601 1
364 2 620 1
97 2 403 1
27 1 ...

output:

999
39 86 119 255 344 375 515 516 569 576 635 644 674 780 790 809 825 836 848 891 945 1018 1048 1051 1132 1137 1159 1182 1185 1244 1254 1334 1369 1408 1449 1493 1524 1528 1538 1567 1573 1586 1594 1607 1711 1727 1756 1768 1772 1811 1723 1363 994 1644 312 694 893 1041 851 894 1693 1055 1806 1651 501 7...

result:

ok Correct. (200 test cases)

Test #14:

score: 0
Accepted
time: 90ms
memory: 6672kb

input:

200
745 1668
10 1 215 2
136 2 337 1
528 1 727 2
287 1 314 2
93 1 692 2
37 2 497 1
577 2 597 1
100 1 306 2
313 1 743 2
421 1 597 2
313 1 342 2
236 2 305 1
198 1 617 2
52 1 156 2
144 2 368 1
170 1 428 2
209 1 241 2
125 1 306 2
381 2 715 1
37 1 156 2
395 2 581 1
186 2 580 1
81 1 216 2
120 1 306 2
251 2...

output:

1012
81 94 102 113 152 197 225 248 282 284 286 345 369 379 431 511 521 662 670 701 707 744 757 804 851 861 866 890 905 924 976 1022 1024 1049 1086 1126 1127 1134 1136 1142 1209 1214 1228 1340 1403 1437 1469 1485 1490 1578 1421 1053 1027 1520 1251 478 220 75 782 435 303 122 1217 406 1554 1468 1008 16...

result:

ok Correct. (200 test cases)

Test #15:

score: 0
Accepted
time: 199ms
memory: 18884kb

input:

4
74995 97040
23497 1 31972 2
8788 2 69397 1
51522 2 62220 1
9584 1 11674 2
13370 2 36146 1
39507 1 74477 2
1427 1 33348 2
11493 2 13101 1
32701 2 40560 1
28485 1 47620 2
17874 2 62375 1
20454 2 66633 1
13755 2 61191 1
12861 2 63188 1
52357 1 67165 2
12934 1 59450 2
14794 1 17744 2
61153 1 69340 2
8...

output:

99836
194 1162 1795 3167 3284 3970 5090 7709 12750 13515 15432 15498 16754 16927 20036 20714 23133 27037 27118 28938 31136 31294 31393 31939 33032 36376 36430 39624 40558 41384 42098 42225 42293 42510 42956 43899 44070 44668 45203 47935 48106 48211 49049 50974 52861 52934 55251 55325 56326 56834 584...

result:

ok Correct. (4 test cases)

Test #16:

score: 0
Accepted
time: 212ms
memory: 20840kb

input:

4
74988 97757
6254 1 14126 2
2960 2 7884 1
264 1 26963 2
16894 1 73361 2
40794 2 62973 1
15845 1 45281 2
26578 1 61068 2
14464 2 40449 1
60333 1 73068 2
15459 2 72767 1
44940 2 46205 1
56974 1 65823 2
673 1 12086 2
31184 2 60179 1
924 1 72427 2
22116 2 30494 1
39764 1 50149 2
8984 2 34549 1
47283 1 ...

output:

99896
361 1584 2469 2722 3462 3774 3795 4502 5162 5938 6422 7386 7453 8192 8337 10883 11350 12459 13450 14967 16973 17615 18813 20716 21642 21819 22634 24351 26998 27669 27802 28781 29832 32892 33167 35838 35954 37118 38647 38763 40793 41590 42532 42845 43057 46302 47073 47262 47513 47758 48035 4834...

result:

ok Correct. (4 test cases)

Test #17:

score: 0
Accepted
time: 280ms
memory: 30004kb

input:

2
150000 197734
56160 1 148935 2
14203 2 142849 1
141811 2 149919 1
12846 1 140822 2
32811 2 104214 1
37237 2 73067 1
39554 1 58164 2
17623 1 30566 2
45475 1 88051 2
2948 1 36363 2
121185 1 130780 2
43705 2 139248 1
105491 2 114240 1
22905 2 102102 1
52418 2 85590 1
85614 1 142446 2
145002 2 148378 ...

output:

200477
824 1260 1378 1511 2534 2540 2837 3009 4948 7223 7993 8018 8167 8210 8435 8487 8720 8791 8985 9282 9640 10134 10759 10812 11302 12035 12613 12847 13917 15146 15404 15844 15876 17550 17917 18622 18848 18898 19300 20443 20497 21271 21731 21782 22329 22757 22842 23747 23810 24608 24864 24872 249...

result:

ok Correct. (2 test cases)

Test #18:

score: 0
Accepted
time: 247ms
memory: 31116kb

input:

2
149994 189488
105606 1 132955 2
36574 1 86107 2
101018 2 113530 1
122540 2 143227 1
16632 2 89793 1
25443 1 149904 2
99976 2 136760 1
10596 2 112318 1
84455 1 132258 2
85919 2 93042 1
42680 2 68046 1
60230 2 112109 1
30417 1 79467 2
72216 1 109099 2
24431 2 26346 1
31235 1 109427 2
100973 2 114543...

output:

198916
139 187 603 725 826 901 948 1362 1492 1629 2338 2445 2543 3121 3365 3739 4439 5502 7263 7848 8034 8284 9160 9448 10213 10424 10673 11368 11386 11592 11664 11986 12076 13001 13234 13404 14579 14626 14805 14965 15374 15474 16100 16193 16470 17053 17511 18034 18109 18808 19220 19490 20893 21126 ...

result:

ok Correct. (2 test cases)

Test #19:

score: 0
Accepted
time: 308ms
memory: 52304kb

input:

1
299998 436956
66759 1 261790 2
109661 2 298655 1
46487 1 170884 2
76196 2 124936 1
70653 1 154152 2
187319 1 250381 2
131759 1 133674 2
153676 1 231765 2
95797 1 282385 2
95776 1 187606 2
6703 2 106783 1
251760 2 267115 1
54769 2 192966 1
115099 2 180310 1
192901 2 250903 1
35909 2 295379 1
22399 ...

output:

394765
1312 1353 2474 4017 5159 6031 6250 8062 8981 10175 10907 10987 13019 13119 13441 14451 14873 15068 15458 15954 15980 16482 17223 18097 18176 18183 18812 19466 20611 23576 24090 27599 27713 28487 28518 29074 29234 29495 31197 31650 32288 34575 34695 36631 38654 39983 40491 41397 41410 43692 44...

result:

ok Correct. (1 test case)

Test #20:

score: 0
Accepted
time: 303ms
memory: 49576kb

input:

1
299994 438245
38127 2 88766 1
59431 1 233331 2
225189 2 299437 1
76723 2 250018 1
80328 1 284489 2
135816 2 296190 1
27764 2 225748 1
57528 2 199070 1
60742 1 139855 2
129082 1 134585 2
72351 1 177898 2
6906 1 35622 2
33083 2 135388 1
92785 2 180981 1
102084 2 111670 1
116574 1 276018 2
113641 2 2...

output:

362332
1286 1581 1850 2013 2112 4890 5025 5603 5930 6313 7182 8390 8918 9004 9210 9278 11590 11653 14442 15149 15208 15964 16708 17524 17613 18254 19027 19231 20695 22003 23384 23637 24599 28005 29046 29247 29817 31383 34187 34240 35412 38219 39118 39905 41064 41560 43043 43289 44605 45145 46604 475...

result:

ok Correct. (1 test case)

Test #21:

score: 0
Accepted
time: 348ms
memory: 56440kb

input:

1
299998 498452
39091 2 59969 1
15828 2 270690 1
163349 2 191051 1
42486 1 110810 2
30384 1 223902 2
75185 1 269916 2
56964 2 162885 1
98233 2 196058 1
116601 1 127054 2
85919 1 102077 2
196200 2 214656 1
54709 1 265378 2
87175 1 234557 2
15966 1 21852 2
197173 1 277230 2
48503 2 49594 1
67349 2 242...

output:

400616
718 1314 3855 4040 4239 5545 6566 7335 8193 9454 9636 10126 10521 10907 11185 12321 14367 14688 14800 16368 18000 18564 19213 19663 19665 21811 22053 22183 23007 24694 27659 28158 28397 31783 32465 33094 33649 33679 35255 36623 36715 37101 37707 37848 38651 38960 41855 41876 43798 43858 44277...

result:

ok Correct. (1 test case)

Test #22:

score: 0
Accepted
time: 358ms
memory: 54232kb

input:

1
299995 499550
77642 2 123304 1
18605 1 73000 2
172858 1 248852 2
232126 2 281373 1
42007 2 117419 1
223100 2 257268 1
20588 1 213881 2
221459 2 249009 1
151591 2 176060 1
192169 1 210466 2
33033 1 83266 2
149863 2 281213 1
201519 1 223370 2
166375 1 193359 2
9628 2 156701 1
174303 2 207866 1
24592...

output:

400646
2015 3727 4830 5504 6405 9988 10394 10923 11395 13762 14922 16054 17868 18281 18858 18892 19660 20431 22752 23355 23433 24451 24547 28188 30831 31954 34386 34934 35333 35654 36292 36342 37922 44217 44476 44520 46196 47636 47713 47933 48104 48125 48534 48760 49016 49037 49909 50633 53014 54154...

result:

ok Correct. (1 test case)

Test #23:

score: -100
Runtime Error

input:

1
500000 499975
309101 2 498946 1
281120 2 349107 1
196611 1 428634 2
366844 1 454632 2
99985 2 491559 1
463849 2 481265 1
15616 2 149720 1
217051 2 272193 1
170421 2 180431 1
286108 1 319941 2
35639 1 479590 2
119301 2 472138 1
143961 2 234120 1
76549 1 381510 2
308177 2 334281 1
320444 2 467256 1
...

output:


result: