# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
26590918 |
Practice:
tcchung |
780G
- 17
|
C++14 (GCC 6-32)
|
Accepted
|
202 ms
|
64012 KB
|
2017-04-22 22:52:24 |
2017-04-22 22:52:24 |
|
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int M = 1e9+7;
const int N = 1e5+10;
stack<pair<int,int>> S[N];
pair<int,int> ST[2*N];
int h,w,n;
tuple<int,int,int,int> B[N];
int u,l,r,s,ans;
void updateST(int p) {
ST[p+w] = {S[p].top().first,p};
for (p+=w;p>1;p>>=1)
ST[p/2] = min(ST[p],ST[p^1]);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> h >> w >> n;
ans = w;
for (int i=0;i<n;i++)
cin >> get<0>(B[i]) >> get<1>(B[i]) >> get<2>(B[i]) >> get<3>(B[i]);
sort(B,B+n,greater<tuple<int,int,int,int>>());
for (int i=0;i<w;i++) ST[w+i] = {h+1,i};
for (int i=w-1;i>0;i--) ST[i] = min(ST[2*i],ST[2*i+1]);
for (int i=0;i<w;i++) S[i].push({h+2,0});
for (int i=0;i<w;i++) S[i].push({h+1,1});
for (int i=0;i<n;i++) {
ll cnt = 0;
tie(u,l,r,s) = B[i];
l--; r--;
bool done;
do {
done = true;
int lt = l+w;
int rt = r+w;
pair<int,int> minNode = {h+2,0};
while (lt <= rt) {
if (lt&1) {
minNode = min(minNode,ST[lt]);
lt++;
}
lt >>= 1;
if (rt%2 == 0) {
minNode = min(minNode,ST[rt]);
rt--;
}
rt >>= 1;
}
if (minNode.first <= min(h+1,u+s)) {
int p = minNode.second;
cnt = (cnt + S[p].top().second) % M;
S[p].pop();
updateST(p);
done = false;
}
} while (!done);
if (cnt) {
if (l == 0) {
S[r+1].push({u,2*cnt%M});
updateST(r+1);
}
else if (r == w-1) {
S[l-1].push({u,2*cnt%M});
updateST(l-1);
}
else {
S[r+1].push({u,cnt});
updateST(r+1);
S[l-1].push({u,cnt});
updateST(l-1);
}
ans = (ans + cnt)%M;
}
}
cout << ans << endl;
return 0;
}
Click to see test details