QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662296 | #7752. The Only Way to the Destination | zrj66 | WA | 0ms | 3580kb | C++20 | 3.9kb | 2024-10-20 22:39:39 | 2024-10-20 22:39:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
using i128 = __int128;
using i64 = long long;
struct Node {
int val = 0, tag = 0;
Node *l = nullptr;
Node *r = nullptr;
};
void up(Node *p) {
if (!p->l)
p->val = p->r->val;
else if (!p->r)
p->val = p->l->val;
else
p->val = p->l->val + p->r->val;
}
void down(Node *p, int l, int r) {
if (p->tag == 0)
return;
int mid = l + r >> 1;
if (!p->l)
p->l = new Node();
if (!p->r)
p->r = new Node();
int b = p->tag;
p->l->val += b * (mid - l + 1);
p->r->val += b * (r - mid);
p->l->tag += b;
p->r->tag += b;
p->tag = 0;
}
void modify(Node *&p, int l, int r, int tl, int tr) {
if (!p)
p = new Node();
if (tl <= l and r <= tr) {
p->val += r - l + 1;
p->tag++;
return;
}
down(p, l, r);
int mid = l + r >> 1;
if (tl <= mid)
modify(p->l, l, mid, tl, tr);
if (mid < tr)
modify(p->r, mid + 1, r, tl, tr);
up(p);
}
int get(Node *p, int l, int r, int tl, int tr) {
if (!p)
return 0;
if (tl <= l and r <= tr) {
return p->val;
}
down(p, l, r);
int mid = l + r >> 1, ans = 0;
if (tl <= mid)
ans = get(p->l, l, mid, tl, tr);
if (mid < tr)
ans += get(p->r, mid + 1, r, tl, tr);
return ans;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, k;
std::cin >> n >> m >> k;
m = min(m, 601000);
std::vector<std::array<int, 3>> wall(k);
for (auto &[xl, xr, y] : wall) {
std::cin >> xl >> xr >> y;
}
std::vector wallArr(m + 1, std::vector<std::pair<int, int>>());
for (auto [xl, xr, y] : wall) {
if(y <= m) wallArr[y].push_back({xl, xr});
}
i64 totv = 1ll * n * m, totb = 2ll * n * m - n - m;
Node *rt = new Node();
for(int i = 1; i <= m; i ++){
if(i == 1 || i == m){
std::sort(wallArr[i].begin(), wallArr[i].end());
for (int j = 0; j < wallArr[i].size(); j++) {
auto [l, r] = wallArr[i][j];
totv -= r - l + 1;
totb += get(rt, 1, n, l, r) - (r - l + 2);
totb -= 2 * (r - l + 1);
if (i == 1)
totb += r - l + 1;
if (i == m)
totb += r - l + 1;
if (j and wallArr[i][j - 1].second + 1 == l)
totb ++;
if (j == 1 and l == 1)
totb ++;
if (r == n)
totb ++;
}
}
else{
int last = 0;
sort(wallArr[i].begin(), wallArr[i].end());
// cout << stk[i].size() << "\n";
for(auto [x1, x2] : wallArr[i]){
int t = get(rt, 1, n, x1, x2);
int len = x2 - x1 + 1;
// cout << x1 << " " << x2 << " " << t << " " << len << "\n";
totv -= len;
totb += t;
totb -= len * 2;
totb -= len + 1;
if(last == x1) totb ++;
if(x1 == 1) totb ++;
if(x2 == n) totb ++;
last = x2 + 1;
}
}
rt = new Node();
for (auto [l, r] : wallArr[i]) {
modify(rt, 1, n, l, r);
}
}
std::cout << (totb + 1 == totv ? "YES" : "NO");
}
/*
3 3 3
1 1 1
3 3 1
2 2 3
6 5 5
1 2 5
1 6 2
5 6 2
4 5 3
4 6 5
7 4 6
3 6 1
2 2 2
7 7 2
1 1 3
2 2 3
7 7 3
4 6 6
4 4 1
1 2 2
4 4 3
1 2 4
4 4 5
1 2 6
7 7 9
1 7 1
1 3 2
5 7 2
1 1 3
3 3 3
3 6 4
2 3 5
7 7 6
2 5 6
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3580kb
input:
5 3 2 2 5 1 1 4 3
output:
NO
result:
wrong answer expected YES, found NO