oj.uz

Submission #218832

# Submission time Handle Problem Language Result Execution time Memory
218832 2020-04-02T19:37:51 Z VEGAnn New Home (APIO18_new_home) C++14
0 / 100
 10 ms 7424 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define MP make_pair
#define PB push_back
#define pii pair<int,int>
#define pi3 pair<pii,int>
#define ft first
#define sd second
#define sz(x) ((int)x.size())
using namespace std;
const int N = 300100;
const int oo = int(2e9) + 7;
vector<int> vc[N];
vector<pii> qr;
int n, k, q, ans[N], l[N];
bool was = 0;
 
bool bigger(pii a, pii b){
    b.sd -= (a.ft - b.ft);
    return b.sd > a.sd;
}
 
void check(){
    qr.clear();
 
    for (int i = 0; i < k; i++){
        qr.PB(MP(0, -vc[i][0]));
 
        for (int it = 1; it < sz(vc[i]); it++){
            int len = (vc[i][it] - vc[i][it - 1]);
            qr.PB(MP(len / 2 + vc[i][it - 1], -len / 2));
        }
    }
   
    for (int i = 0; i < q; i++)
        qr.PB(MP(l[i], i + 1));
 
    sort(all(qr));
  
  if (was) exit(0);
 
    pii mx = MP(0, 0);
 
    for (pii cr : qr)
        if (cr.sd <= 0){
            cr.sd = -cr.sd;
            if (bigger(mx, cr))
                mx = cr;
        } else {
            ans[cr.sd - 1] = max(ans[cr.sd - 1], mx.sd - (cr.ft - mx.ft));
        }
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
 
    freopen("in.txt","r",stdin);
 
    cin >> n >> k >> q;
 
    for (int i = 0; i < n; i++) {
        int j, t, x;
        cin >> x >> t >> j >> j;
        x += x;
        t--;
        vc[t].PB(x);
    }
 
    for (int i = 0; i < k; i++) {
        if (sz(vc[i]) == 0){
            for (; q; q--) cout << "-1\n";
            return 0;
        }
 
        sort(all(vc[i]));
    }
 
    for (int i = 0; i < q; i++) {
        int j;
        cin >> l[i] >> j;
        l[i] += l[i];
        ans[i] = 0;
    }
 
    check();
 
    for (int i = 0; i < q; i++)
        l[i] = int(2e8) - l[i];
 
    for (int i = 0; i < k; i++)
        for (int &cr : vc[i]) {
            cr = int(2e8) - cr;
        }
 
  was = 1;
    check();
 
    for (int i = 0; i < q; i++)
        cout << (ans[i] == oo ? -1 : ans[i] / 2) << '\n';
 
    return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("in.txt","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -