#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int N, M;
int L[100005];
int R[100005];
int val[100005];
array<int, 3> A[100005];
struct SegTree {
struct Node {
int mi, p;
Node():mi(0), p(0) {}
Node(int _m, int _p) : mi(_m), p(_p) {}
};
vector<Node> seg;
int MAX;
SegTree(int N) {
int i;
for(i=1;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
}
void cons() {
for(int i = MAX/2-1;i>=1;i--) {
seg[i].mi = min(seg[2*i].mi, seg[2*i+1].mi);
}
}
void prop(int n, int ns, int ne) {
if(seg[n].p) {
seg[n].mi += seg[n].p;
if(n < MAX/2) {
seg[2*n].p += seg[n].p;
seg[2*n+1].p += seg[n].p;
}
seg[n].p = 0;
}
}
void add(int s, int e, int k, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return;
if(s<=ns&&ne<=e) {
seg[n].p += k;
prop(n,ns,ne);
return;
}
int mid = ns + ne >> 1;
add(s, e, k, 2*n, ns, mid);
add(s, e, k, 2*n+1, mid, ne);
if(n<MAX/2) seg[n].mi = min(seg[2*n].mi, seg[2*n+1].mi);
}
int sum(int s, int e, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return INF;
if(s<=ns&&ne<=e) return seg[n].mi;
int mid = ns + ne >> 1;
return min(sum(s, e, 2*n, ns, mid), sum(s, e, 2*n+1, mid, ne));
}
};
int Q1[100005];
int Q2[100005];
bool isPos(int c) {
//cout << "isPos " << c << '\n';
int i, j;
for(i=0;i<M;i++) val[i] = -1;
for(i=0;i<N;i++) L[i] = M, R[i] = -1;
for(i=0;i<c;i++) {
if(val[A[i][0]]==-1) val[A[i][0]] = A[i][2];
else if(val[A[i][0]] != A[i][2]) return false;
L[A[i][1]] = min(L[A[i][1]], A[i][0]);
R[A[i][1]] = max(R[A[i][1]], A[i][0]);
}
//cout << "step 1\n";
int free = 0;
for(i=0;i<M;i++) Q1[i] = Q2[i] = 0;
for(i=0;i<N;i++) {
if(R[i]==-1) free++;
else {
Q1[L[i]]++;
Q2[R[i]]++;
}
}
/*for(i=0;i<M;i++) {
cout << val[i] << ' ';
}
cout << '\n';*/
int m = 0;
int must = 0;
SegTree tree(M+3);
int MAX = tree.MAX;
for(i=0;i<M;i++) {
int v = (val[i] == -1 ? INF : val[i]);
tree.seg[i+MAX/2].mi = v;
}
tree.cons();
for(i=0;i<N;i++) {
if(R[i]!=-1) {
tree.add(L[i], R[i]+1, -1, 1, 0, MAX/2);
}
}
int pt = 0;
for(i=0;i<M;i++) {
//cout << i << " : " << val[i] << '\n';
if(pt == i) {
must += Q1[pt];
m += Q1[pt];
pt++;
}
if(val[i]==-1) continue;
if(m >= val[i]) {
m = min(m, val[i]);
if(m < must) return false;
}
else {
while(pt < M && m < val[i]) {
if(Q1[pt] == 0) {
pt++;
continue;
}
int v = tree.sum(i, pt, 1, 0, MAX/2);
if(v <= 0) break;
v = min(v, Q1[pt]);
v = min(v, val[i] - m);
tree.add(i, pt, -v, 1, 0, MAX/2);
must+=v;
m+=v;
Q1[pt] -= v;
if(Q1[pt]==0) pt++;
}
if(m < val[i]) {
free -= val[i] - m;
m = val[i];
if(free < 0) return false;
}
}
must -= Q2[i];
}
return true;
}
void solve() {
N = 100000, M = 100000;
cin >> N >> M;
int i, j;
for(i=0;i<M;i++) {
int a, b, c;
a = i+1, b = i+1, c = 1;
cin >> a >> b >> c;
a--, b--;
A[i] = {a, b, c+1};
}
int s = 0, e = M;
while(s+1<e) {
int mid = (s+e)/2;
if(isPos(mid+1)) s = mid;
else e = mid;
}
cout << s+1 << '\n';
}
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
clock_t st = clock();
while(t--) {
solve();
}
//cout << '\n' << clock() - st << "ms";
}
Compilation message
ins.cpp: In member function 'void SegTree::add(int, int, int, int, int, int)':
ins.cpp:46:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int mid = ns + ne >> 1;
| ~~~^~~~
ins.cpp: In member function 'int SegTree::sum(int, int, int, int, int)':
ins.cpp:55:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int mid = ns + ne >> 1;
| ~~~^~~~
ins.cpp: In function 'bool isPos(int)':
ins.cpp:63:12: warning: unused variable 'j' [-Wunused-variable]
63 | int i, j;
| ^
ins.cpp: In function 'void solve()':
ins.cpp:142:12: warning: unused variable 'j' [-Wunused-variable]
142 | int i, j;
| ^
ins.cpp: In function 'int main()':
ins.cpp:164:13: warning: unused variable 'st' [-Wunused-variable]
164 | clock_t st = clock();
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
3 ms |
340 KB |
Output is correct |
| 5 |
Correct |
10 ms |
372 KB |
Output is correct |
| 6 |
Correct |
23 ms |
340 KB |
Output is correct |
| 7 |
Correct |
37 ms |
340 KB |
Output is correct |
| 8 |
Correct |
309 ms |
896 KB |
Output is correct |
| 9 |
Correct |
656 ms |
1484 KB |
Output is correct |
| 10 |
Correct |
1645 ms |
2672 KB |
Output is correct |
| 11 |
Correct |
1812 ms |
3004 KB |
Output is correct |
| 12 |
Correct |
4652 ms |
5488 KB |
Output is correct |
| 13 |
Correct |
3174 ms |
5484 KB |
Output is correct |
