QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #389044 | #6703. Tokens on the Segments | Mayuri | WA | 81ms | 6816kb | C++14 | 2.7kb | 2024-04-14 00:29:56 | 2024-04-14 00:29:56 |
Judging History
answer
//#define _CRT_SECURE_NO_WARNINGS
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//typedef long double ld;
//#define endl '\n'
//const ll maxn = 2e5 + 5;
//ll T;
//ll n, m, k;
//ll u[maxn], v[maxn];
//
//int main()//D
//{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// cin >> T;
// while (T--) {
// cin >> k;
// string s; cin >> s;
// cin >> n >> m;
// for (ll i = 1; i <= m; i++) {
// ll u, v; cin >> u >> v;
// }
// ll d = m - n + 2;
// d--;
// ll t = d % k;
// if (s[t] == '1') cout << 2 << endl;
// else cout << 1 << endl;
// }
//}
//#define _CRT_SECURE_NO_WARNINGS
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//typedef long double ld;
//#define endl '\n'
//const ll maxn = 2e5 + 5;
//ll T;
//ll n, m, k;
//ll u[maxn], v[maxn];
//ll dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
//ll f(char ch) {
// if (ch == 'U')return 0;
// if (ch == 'R')return 1;
// if (ch == 'D')return 2;
// if (ch == 'L')return 3;
//}
//int main()//C
//{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// cin >> T;
// while (T--) {
// cin >> n >> k;
// string s; cin >> s;
// ll bx = 0, by = 0;
// ll mx = 0, my = 0;
// ll mmax = 0;
// for (ll i = 0; i < s.size(); i++) {
// ll t = f(s[i]);
// bx += dx[t];
// by += dy[t];
// if (abs(bx) + abs(by) > abs(mx) + abs(my)) {
// mx = bx;
// my = by;
// }
// }
// bx = bx * (k - 1);
// by = by * (k - 1);
// ll tx = 0, ty = 0;
// for (ll i = 0; i < s.size(); i++) {
// ll t = f(s[i]);
// bx += dx[t];
// by += dy[t];
// if (abs(bx) + abs(by) > abs(tx) + abs(ty)) {
// tx = bx;
// ty = by;
// }
// }
// cout << max(abs(tx) + abs(ty), abs(mx) + abs(my)) << endl;
// }
//}
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define endl '\n'
const ll maxn = 2e5 + 5;
ll T;
ll n, m;
struct node {
ll l, r;
bool operator<(node t)const {
if (l == t.l) return r < t.r;
return l < t.l;
}
}N[maxn];
int main()//C
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--) {
cin >> n;
for (ll i = 1; i <= n; i++) cin >> N[i].l >> N[i].r;
sort(N + 1, N + 1 + n);
ll cur = -1;
ll p = 1;
ll ans = 0;
priority_queue<ll, vector<ll>, greater<ll>>q;
while (p <= n) {
if (q.empty()) cur = N[p].l;
while (p <= n && cur == N[p].l) {
q.push(N[p].r);
p++;
}
while (q.size() && q.top() < cur)q.pop();
if (q.size() && cur <= q.top())ans++, q.pop();
cur++;
}
while (q.size() && q.top() >= cur) {
q.pop();
ans++;
cur = cur + 1;
}
cout << ans << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3652kb
input:
2 3 1 2 1 1 2 3 3 1 2 1 1 2 2
output:
3 2
result:
ok 2 number(s): "3 2"
Test #2:
score: -100
Wrong Answer
time: 81ms
memory: 6816kb
input:
10000 6 5 19 7 12 10 10 4 14 1 12 5 11 7 3 5 1 10 12 15 2 13 8 11 5 20 11 14 18 6 17 6 9 6 20 2 7 1 11 16 19 2 5 1 14 5 8 14 19 4 7 11 19 11 13 2 9 3 12 12 13 19 19 13 16 11 11 13 1 2 14 17 15 16 12 17 15 17 6 7 8 11 12 19 3 8 10 19 18 6 9 16 18 13 15 14 15 9 13 2 8 12 18 8 16 16 18 3 18 1 12 4 13 1...
output:
6 7 18 11 18 12 8 18 16 3 4 5 9 18 14 18 18 13 8 17 16 19 11 17 11 14 4 13 13 3 5 15 9 3 17 8 8 15 7 20 4 11 18 19 6 13 14 12 20 10 6 6 11 7 13 12 19 3 16 17 14 14 7 6 6 11 13 13 3 5 3 4 10 6 3 7 19 14 13 4 9 8 15 19 10 11 10 8 4 18 20 8 19 10 18 18 13 11 6 16 16 18 10 6 8 8 9 16 8 14 14 15 13 17 18...
result:
wrong answer 16th numbers differ - expected: '19', found: '18'