Submission #1143290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143290		snpmrnhlol	Inspector (POI13_ins)	C++20	7 / 100	5094 ms	3960 KiB

ins

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int inf = 1e9;
struct ev{
    int t, id, others; 
}e[N];
int st[N], en[N];
int v2[N];
map <int, int> f;
void add(int l, int r, int x){
    for(int i = l;i <= r;i++){
        v2[i]+=x;
    }
}
void solve(){
    int n, m;
    int ans;
    cin>>n>>m;
    ans = m;
    f.clear();
    for(int i = 0;i < n;i++){
        st[i] = m + 1;
        en[i] = -1;
    }
    for(int i = 0;i < m;i++){
        v2[i] = 0;
    }
    for(int i = 0;i < m;i++){
        cin>>e[i].t>>e[i].id>>e[i].others;
        e[i].t--;
        if(f.find(e[i].t) != f.end() && f[e[i].t] != e[i].others + 1){
            ans = min(ans, i);
            //cout<<"i1\n";
        }
        f[e[i].t] = e[i].others + 1;
        e[i].id--;
        /// apply update
        if(st[e[i].id] != m + 1){
            add(st[e[i].id], en[e[i].id], -1);
        }
        st[e[i].id] = min(st[e[i].id], e[i].t);
        en[e[i].id] = max(en[e[i].id], e[i].t);
        add(st[e[i].id], en[e[i].id], 1);
        int mnppl = 0, prv = 0;
        for(auto j : f){
            if(j.second < v2[j.first]){
                ans = min(ans, i);
                //cout<<"i2\n";
            }
            mnppl+=max(0, j.second - prv);
            prv = j.second;
        }
        if(mnppl > n){
            ans = min(ans, i);
            //cout<<"i3\n";
        }
    }
    cout<<ans<<'\n';
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
/**
2
3 5
1 1 1
1 2 1
2 3 1
4 1 1
4 2 1
3 3
3 3 0
2 2 0
1 1 0

 **/

• Subtask 1: 7 / 100