Submission #699013

# Submission time Handle Problem Language Result Execution time Memory
699013 2023-02-15T10:25:13 Z Cross_Ratio Inspector (POI13_ins) C++14
0 / 100
3919 ms 10708 KB
#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

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();
      |             ^~
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 2 ms 340 KB Output isn't correct
5 Incorrect 11 ms 408 KB Output isn't correct
6 Incorrect 19 ms 340 KB Output isn't correct
7 Incorrect 28 ms 544 KB Output isn't correct
8 Incorrect 269 ms 1468 KB Output isn't correct
9 Incorrect 617 ms 2536 KB Output isn't correct
10 Incorrect 1548 ms 5012 KB Output isn't correct
11 Incorrect 1432 ms 5516 KB Output isn't correct
12 Incorrect 3919 ms 10708 KB Output isn't correct
13 Incorrect 2667 ms 10672 KB Output isn't correct