QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#662296#7752. The Only Way to the Destinationzrj66WA 0ms3580kbC++203.9kb2024-10-20 22:39:392024-10-20 22:39:39

Judging History

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

  • [2024-10-20 22:39:39]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3580kb
  • [2024-10-20 22:39:39]
  • 提交

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

*/

详细

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