Submission #699013

#	Time	Username	Problem	Language	Result	Execution time	Memory
699013		Cross_Ratio	Inspector (POI13_ins)	C++14	0 / 100	3919 ms	10708 KiB

ins

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e12;
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(val[i] == -1) continue;
        if(pt == i) {
            must += Q1[pt];
            m += Q1[pt];
            pt++;
        }
        if(m >= val[i]) {
            m = min(m, val[i]);
            if(m < must) return false;
        }
        else {
            while(pt < N && 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 (stderr)

ins.cpp: In member function 'void SegTree::add(long long int, long long int, long long int, long long int, long long int, long long int)':
ins.cpp:47:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
ins.cpp: In member function 'long long int SegTree::sum(long long int, long long int, long long int, long long int, long long int)':
ins.cpp:56:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
ins.cpp: In function 'bool isPos(long long int)':
ins.cpp:64:12: warning: unused variable 'j' [-Wunused-variable]
   64 |     int i, j;
      |            ^
ins.cpp: In function 'void solve()':
ins.cpp:143:12: warning: unused variable 'j' [-Wunused-variable]
  143 |     int i, j;
      |            ^
ins.cpp: In function 'int main()':
ins.cpp:165:13: warning: unused variable 'st' [-Wunused-variable]
  165 |     clock_t st = clock();
      |             ^~

• Subtask 1: 0 / 100