Submission #571561

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
571561	2022-06-02T11:05:24 Z	Cross_Ratio	New Home (APIO18_new_home)	C++14	10 / 100	1984 ms	210604 KB

new_home

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
int X[300005];
int type[300005];
int A[300005];
int B[300005];
int L[300005];
int Y[300005];
int ans[300005];
int state_a[300005];
int state_b[300005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, K, Q;
    cin >> N >> K >> Q;
    int i, j;
    for(i=0;i<N;i++) cin >> X[i] >> type[i] >> A[i] >> B[i];
    for(i=0;i<N;i++) type[i]--;
    for(i=0;i<Q;i++) cin >> L[i] >> Y[i];
    vector<vector<int>> V;
    V.resize(K);
    for(i=0;i<N;i++) V[type[i]].push_back(X[i]);
    for(i=0;i<K;i++) sort(V[i].begin(),V[i].end());
    bool emp = false;
    for(i=0;i<K;i++) {
        if(V[i].size()==0) emp = true;
    }
    if(emp) {
        for(i=0;i<Q;i++) cout << "-1\n";
        return 0;
    }
    map<int,int> Minus, Plus;
    for(i=0;i<K;i++) {
        state_a[i] = -1;
        state_b[i] = V[i][0];
        Minus[state_b[i]]++;
    }
    map<int,vector<T>> Query;
    vector<int> idx;
    for(i=0;i<K;i++) {
        for(j=0;j<V[i].size();j++) {
            Query[V[i][j]].push_back(T(i, 1, -V[i][j]));
            idx.push_back(V[i][j]);
        }
        for(j=0;j+1<V[i].size();j++) {
            int mid = (V[i][j] + V[i][j+1] + 1) / 2;
            if(mid == V[i][j+1]) continue;
            Query[mid].push_back(T(i, -1, V[i][j+1]));
            idx.push_back(mid);
        }
    }
    map<int,vector<int>> Qu;
    for(i=0;i<Q;i++) {
        Qu[L[i]].push_back(i);
        idx.push_back(L[i]);
    }
    sort(idx.begin(),idx.end());
    idx.erase(unique(idx.begin(),idx.end()),idx.end());
    for(i=0;i<idx.size();i++) {
        for(T k : Query[idx[i]]) {
            int id = get<0>(k);
            int a = get<1>(k);
            int b = get<2>(k);
            if(state_a[id]==1) {
                Plus[state_b[id]]--;
                if(Plus[state_b[id]]==0) Plus.erase(state_b[id]);
            }
            else {
                Minus[state_b[id]]--;
                if(Minus[state_b[id]]==0) Minus.erase(state_b[id]);
            }
            state_a[id] = a;
            state_b[id] = b;
            if(state_a[id]==1) {
                Plus[b]++;
            }
            else {
                Minus[b]++;
            }
        }
        for(int m : Qu[idx[i]]) {
            int m1 = -1e18;
            int m2 = -1e18;
            if(!Plus.empty()) m1 = Plus.rbegin()->first;
            if(!Minus.empty()) m2 = Minus.rbegin()->first;
            ans[m] = max(idx[i] + m1, -idx[i] + m2);
        }
    }
    for(i=0;i<Q;i++) cout << ans[i] << '\n';
    /*
    vector<map<int,int>> S;
    S.resize(K);
    map<int,vector<P>> In;
    map<int,vector<P>> Out;
    for(i=0;i<N;i++) {
        type[i]--;
        In[A[i]].push_back(P(type[i],X[i]));
        Out[B[i]].push_back(P(type[i],X[i]));
    }
    map<int,vector<P>> Query;
    for(i=0;i<Q;i++) {
        Query[Y[i]].push_back(P(L[i],i));
    }
    vector<int> idx;
    for(i=0;i<Q;i++) idx.push_back(Y[i]);
    for(i=0;i<N;i++) {
        idx.push_back(A[i]);
        idx.push_back(B[i]);
    }
    sort(idx.begin(),idx.end());
    idx.erase(unique(idx.begin(),idx.end()),idx.end());
    for(i=0;i<idx.size();i++) {
        for(P k : In[idx[i]]) {
            S[k.first][k.second]++;
            //S[k.first].insert(k.second);
        }
        for(P k : Query[idx[i]]) {
            int ma = 0;
            int pos = k.first;
            for(j=0;j<K;j++) {
                int dis = 1e18;
                auto it = S[j].lower_bound(pos);
                if(it != S[j].end()) dis = min(dis, it->first - pos);
                if(it != S[j].begin()) {
                    it--;
                    dis = min(dis, pos - it->first);
                }
                ma = max(ma, dis);
            }
            ans[k.second] = (ma > 1e9 ? -1 : ma);
        }
        for(P k : Out[idx[i]]) {
            S[k.first][k.second]--;
            if(S[k.first][k.second]==0) {
                S[k.first].erase(k.second);
            }
        }
    }
    for(i=0;i<Q;i++) cout << ans[i] << '\n';*/
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:46:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(j=0;j<V[i].size();j++) {
      |                 ~^~~~~~~~~~~~
new_home.cpp:50:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(j=0;j+1<V[i].size();j++) {
      |                 ~~~^~~~~~~~~~~~
new_home.cpp:64:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(i=0;i<idx.size();i++) {
      |             ~^~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Incorrect	1 ms	340 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Incorrect	1 ms	340 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1882 ms	194340 KB	Output is correct
2	Correct	1169 ms	208724 KB	Output is correct
3	Correct	1393 ms	190352 KB	Output is correct
4	Correct	1780 ms	204096 KB	Output is correct
5	Correct	920 ms	208156 KB	Output is correct
6	Correct	988 ms	208500 KB	Output is correct
7	Correct	1247 ms	190468 KB	Output is correct
8	Correct	1724 ms	203492 KB	Output is correct
9	Correct	1763 ms	209316 KB	Output is correct
10	Correct	1557 ms	210604 KB	Output is correct
11	Correct	995 ms	206124 KB	Output is correct
12	Correct	1264 ms	209440 KB	Output is correct