Submission #699018

# Submission time Handle Problem Language Result Execution time Memory
699018 2023-02-15T10:32:06 Z Cross_Ratio Inspector (POI13_ins) C++14
0 / 100
1049 ms 4508 KB
#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 {
    vector<int> 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] = min(seg[2*i], seg[2*i+1]);
        }
    }
    int sum(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return INF;
        if(s<=ns&&ne<=e) return seg[n];
        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] = v;
    }
    tree.cons();
    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 < must + 1) break;
                v -= must;
                v = min(v, Q1[pt]);
                v = min(v, val[i] - m);
                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 'int SegTree::sum(int, int, int, int, int)':
ins.cpp:26:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
ins.cpp: In function 'bool isPos(int)':
ins.cpp:34:12: warning: unused variable 'j' [-Wunused-variable]
   34 |     int i, j;
      |            ^
ins.cpp: In function 'void solve()':
ins.cpp:108:12: warning: unused variable 'j' [-Wunused-variable]
  108 |     int i, j;
      |            ^
ins.cpp: In function 'int main()':
ins.cpp:130:13: warning: unused variable 'st' [-Wunused-variable]
  130 |     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 1 ms 340 KB Output isn't correct
5 Incorrect 4 ms 340 KB Output isn't correct
6 Incorrect 8 ms 388 KB Output isn't correct
7 Incorrect 12 ms 424 KB Output isn't correct
8 Incorrect 81 ms 764 KB Output isn't correct
9 Incorrect 180 ms 1164 KB Output isn't correct
10 Incorrect 394 ms 2088 KB Output isn't correct
11 Incorrect 442 ms 2404 KB Output isn't correct
12 Incorrect 1049 ms 4456 KB Output isn't correct
13 Incorrect 873 ms 4508 KB Output isn't correct