답안 #699010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
699010	2023-02-15T09:56:18 Z	Cross_Ratio	Inspector (POI13_ins)	C++14	54 / 100	2460 ms	5468 KB

ins

#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));
    }
};
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";
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> PQ1, PQ2;
    int free = 0;
    for(i=0;i<N;i++) {
        if(R[i]==-1) free++;
        else PQ1.push({L[i], 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();
    for(i=0;i<M;i++) {
        //cout << i << " : " << val[i] << '\n';
        if(val[i] == -1) continue;
        while(!PQ1.empty() && PQ1.top()[0] <= i) {
            auto k = PQ1.top();
            PQ1.pop();
            PQ2.push({R[k[1]], k[1]});
            must++;
            m++;
        }
        //cout << m << ' ' << must << ' ' << free << '\n';
        if(m >= val[i]) {
            m = min(m, val[i]);
            if(m < must) return false;
        }
        else {
            while(!PQ1.empty() && m < val[i]) {
                auto k = PQ1.top();
                int id = k[1];
                int v = tree.sum(i, L[id], 1, 0, MAX/2);
                if(v < must+1) break;
                else {
                    PQ1.pop();
                    PQ2.push({R[id], id});
                    must++;
                    m++;
                }
            }
            if(m < val[i]) {
                free -= val[i] - m;
                m = val[i];
                if(free < 0) return false;
            }
        }
        while(!PQ2.empty() && PQ2.top()[0] <= i) {
            PQ2.pop();
            must--;
        }
    }
    return true;
}
void solve() {
    cin >> N >> M;
    int i, j;
    for(i=0;i<M;i++) {
        int a, b, c;
        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;
    while(t--) {
        solve();
    }
}

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:32:12: warning: unused variable 'j' [-Wunused-variable]
   32 |     int i, j;
      |            ^
ins.cpp: In function 'void solve()':
ins.cpp:104:12: warning: unused variable 'j' [-Wunused-variable]
  104 |     int i, j;
      |            ^

Subtask #1

54.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Incorrect	2 ms	340 KB	Output isn't correct
5	Incorrect	7 ms	368 KB	Output isn't correct
6	Incorrect	14 ms	388 KB	Output isn't correct
7	Correct	24 ms	444 KB	Output is correct
8	Incorrect	174 ms	836 KB	Output isn't correct
9	Correct	374 ms	1268 KB	Output is correct
10	Correct	956 ms	2592 KB	Output is correct
11	Correct	958 ms	2580 KB	Output is correct
12	Correct	2460 ms	5280 KB	Output is correct
13	Incorrect	1935 ms	5468 KB	Output isn't correct