oj.uz

Submission #391907

# Submission time Handle Problem Language Result Execution time Memory
391907 2021-04-20T06:00:43 Z blue New Home (APIO18_new_home) C++17
0 / 100
 5000 ms 33552 KB 
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int mx = 300000;

int n, k, q;
int x[mx], t[mx], a[mx], b[mx];
int l[mx], y[mx];

int T(int i)
{
    // cerr << "T(" << i << ")\n";
    if(i < n)
    {
        // cerr << "case 1\n";
        return a[i];
    }
    else if(i < n+q)
    {
        // cerr << "case 2\n";
        // cerr << "i-n " << i-n << ' ' << y[i-n] << '\n';
        return y[i-n];
    }
    else
    {
        // cerr << "case 3\n";
        return b[i-n-q];
    }
}

int main()
{
    cin >> n >> k >> q;

    for(int i = 0; i < n; i++)
    {
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        t[i]--;
    }

    for(int j = 0; j < q; j++) cin >> l[j] >> y[j];

    int I[n+q+n];
    for(int i = 0; i < n+q+n; i++)
        I[i] = i;

    sort(I, I+n+q+n, [] (int r, int s)
    {
        int t1 = T(r);
        int t2 = T(s);
        if(t1 == t2) return r < s;
        else return t1 < t2;
    });

    for(int i:I) cerr << i << ' ' << T(i) << '\n';
    cerr << '\n';

    vector<long long> res(q, 0);

    multiset<int> stores[k];

    for(int i:I)
    {
        cerr << i << '\n';
        if(i < n)
        {
            stores[t[i]].insert(x[i]);
        }
        else if(i < n+q)
        {
            cerr << "query " << i-n << '\n';
            for(int typ = 0; typ < k; typ++)
            {
                int temp = 1e9;
                for(int s: stores[t[typ]])
                {
                    cerr << s << ' ';
                    temp = min(temp, abs(s - l[i-n]));
                }
                cerr << '\n';

                res[i-n] = max(res[i-n], (long long)temp);
            }
            if(res[i-n] == 1e9)
            {
                res[i-n] = -1;
            }
            cerr << '\n';
        }
        else
        {
            stores[t[i-n-q]].erase(stores[t[i-n-q]].find(x[i-n-q]));
        }
    }
    cerr << '\n';

    for(int j = 0; j < q; j++) cout << res[j] << '\n';
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5053 ms 33552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5085 ms 32576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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