QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#643730 | #7752. The Only Way to the Destination | LightFeather | RE | 0ms | 0kb | C++20 | 2.7kb | 2024-10-15 23:31:14 | 2024-10-15 23:31:14 |
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ld long double
#define lll __int128
#define dhm std::fixed<<std::setprecision
#define prq priority_queue
using ll = long long;
using ull = unsigned long long;
int T;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
constexpr int N = 1e5, M = 4e6;
struct SegTree {
int l, r;
int ls, rs, sum, cnt;
}tr[M], tr2[M];
struct node {
int x1, x2;
int y;
} wall[N];
int idx1, idx2;
int n, m, k;
void pushup(int u) {
tr[u].l = tr[tr[u].ls].l, tr[u].r = tr[tr[u].rs].r;
tr[u].sum = tr[tr[u].ls].sum + tr[tr[u].rs].sum;
tr[u].cnt = tr[tr[u].ls].cnt + tr[tr[u].rs].cnt;
}
void modify(int& u, int l, int r, int pl, int pr, int x) {
if(!u) {
u = ++ idx1;
tr[u].l = l, tr[u].r = r;
}
if(pl >= l && pr <= r) {
tr[u].sum += (r - l) * x;
tr[u].cnt += x;
return;
}
int mid = l + r >> 1;
if(pr >= l)
modify(tr[u].ls, l, mid, pl, pr, x);
if(pl <= r)
modify(tr[u].rs, mid + 1, r, pl, pr, x);
pushup(u);
}
int query(int u, int l, int r, int sum) {
if(l == r) {
if(sum <= 0)
return 0;
return (sum + l - 1) / l;
}
int mid = l + r >> 1;
if(tr[tr[u].rs].sum >= sum)
return query(tr[u].rs, mid + 1, r, sum);
return query(tr[u].ls, l, mid, sum - tr[tr[u].rs].sum) + tr[tr[u].rs].cnt;
}
void pushup2(int u) {
tr2[u].l = tr2[tr2[u].ls].l, tr2[u].r = tr2[tr2[u].rs].r;
tr2[u].sum = tr2[tr2[u].ls].sum + tr2[tr2[u].rs].sum;
tr2[u].cnt = tr2[tr2[u].ls].cnt + tr2[tr2[u].rs].cnt;
}
void modify2(int& u, int l, int r, int pl, int pr, int x) {
if(!u) {
u = ++ idx1;
tr2[u].l = l, tr2[u].r = r;
}
if(pl >= l && pr <= r) {
tr2[u].sum += (r - l) * x;
tr2[u].cnt += x;
return;
}
int mid = l + r >> 1;
if(pr >= l)
modify2(tr2[u].ls, l, mid, pl, pr, x);
if(pl <= r)
modify2(tr2[u].rs, mid + 1, r, pl, pr, x);
pushup(u);
}
int query2(int u, int l, int r, int sum) {
if(l == r) {
if(sum <= 0)
return 0;
return (sum + l - 1) / l;
}
int mid = l + r >> 1;
if(tr2[tr2[u].rs].sum >= sum)
return query(tr[u].rs, mid + 1, r, sum);
return query(tr[u].ls, l, mid, sum - tr[tr[u].rs].sum) + tr[tr[u].rs].cnt;
}
vector<node> v1, v2;
void solve(){
cin >> n >> m >> k;
for(int i = 1; i <= k; i ++) {
node t;
cin >> t.x1 >> t.x2 >> t.y;
v1.push_back(t);
}
auto cmp = [&](node a,node b)->bool {
if(a.y == b.y)
return a.x1 < b.x1;
return a.y < b.y;
};
sort(v1.begin(), v2.end(), cmp);
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
T = 1;
//std::cin>>T;
while(T --)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
5 3 2 2 5 1 1 4 3