oj.uz

Submission #143543

# Submission time Handle Problem Language Result Execution time Memory
143543 2019-08-14T14:25:27 Z Swan New Home (APIO18_new_home) C++17
0 / 100
 3305 ms 394028 KB 
#include <bits/stdc++.h>
#define stop system("pause")
#define INP freopen("input.txt","r",stdin)
#define OUTP freopen("solve1.txt","w",stdout)
#define int long long
using namespace std;

struct st{
    int x;
    int t;
    int a;
    int b;
    st(int q,int w,int e,int r){
        x = q;
        t = w;
        a = e;
        b = r;
    }
};

struct st2{
    int l;
    int y;
    int id;
    st2(int a,int b,int c){
        l = a;
        y = b;
        id = c;
    }
};

struct st3{
    int ans;
    int id;
    bool operator<(st3 b)const{
        return id < b.id;
    }
    st3(int a,int b){
        ans = a;
        id = b;
    }
};

const int maxn = 3e6;

unordered_map<int,int> unirl,irl;
vector<st2> query[maxn];
vector<st> del[maxn],add[maxn];
int cnt[maxn];
int n,q,k;
vector<st3> res;

void solve(){
    multiset<int> now;
    int all = 0;
    for(int i(0); i < maxn;i++){
        while(add[i].size()){
            if(cnt[add[i].back().t] == 0){
                all++;
            }
            cnt[add[i].back().t]++;
            now.insert(add[i].back().x);
            add[i].pop_back();
        }
        while(del[i].size()){
            if(cnt[del[i].back().t] == 1){
                all--;
            }
            cnt[del[i].back().t]--;
            now.erase(now.find(del[i].back().x));
            del[i].pop_back();
        }
        for(int j(0); j < query[i].size();j++){
            if(all!=k || !now.size()){
                res.push_back(st3(-1,query[i][j].id));
                continue;
            }
            //cout << irl[i] << ' ' << all << ' ' << now.size() << endl;
            int l,r;
            l = *now.begin();
            r = *(--now.end());
            int x = query[i][j].l;
            //cout << "w " << x << endl;
            res.push_back(st3(max(abs(l-x),abs(r-x)),query[i][j].id));
        }
    }

}

main()
{
    ios_base::sync_with_stdio(0);
    cin >> n >> k >> q;
    multiset<int> s;
    vector<st> v;
    for(int i(0); i < n;i++){
        int x,t,a,b; cin >> x >> t >> a >> b;
        s.insert(a);
        s.insert(b);
        v.push_back(st(x,t,a,b));
    }
    vector<st2> qwe;
    for(int i(0); i < q;i++){
        int l,y; cin >> l >> y;
        s.insert(y);
        qwe.push_back(st2(l,y,i));
    }
    int pnt = 0;
    for(auto& a:s){
        unirl[a] = pnt;
        irl[pnt] = a;
        pnt++;
    }
    for(int i(0); i < v.size();i++){
        del[unirl[v[i].b]+1].push_back(v[i]);
        add[unirl[v[i].a]].push_back(v[i]);
    }
    for(int i(0); i < qwe.size();i++){
        query[unirl[qwe[i].y]].push_back(qwe[i]);
    }
    solve();
    sort(res.begin(),res.end());
    for(int i(0); i < res.size();i++){
        cout << res[i].ans << '\n';
    }
    return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

1 1 1
100000000 1 1 1
1 1
*/

Compilation message

new_home.cpp: In function 'void solve()':
new_home.cpp:73:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j(0); j < query[i].size();j++){
                       ~~^~~~~~~~~~~~~~~~~
new_home.cpp: At global scope:
new_home.cpp:90:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
new_home.cpp: In function 'int main()':
new_home.cpp:114:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < v.size();i++){
                   ~~^~~~~~~~~~
new_home.cpp:118:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < qwe.size();i++){
                   ~~^~~~~~~~~~~~
new_home.cpp:123:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < res.size();i++){
                   ~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 211832 KB Output is correct
2 Correct 213 ms 211780 KB Output is correct
3 Correct 219 ms 211720 KB Output is correct
4 Incorrect 214 ms 211804 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 211832 KB Output is correct
2 Correct 213 ms 211780 KB Output is correct
3 Correct 219 ms 211720 KB Output is correct
4 Incorrect 214 ms 211804 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 211832 KB Output is correct
2 Correct 213 ms 211780 KB Output is correct
3 Correct 219 ms 211720 KB Output is correct
4 Incorrect 214 ms 211804 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 211832 KB Output is correct
2 Correct 213 ms 211780 KB Output is correct
3 Correct 219 ms 211720 KB Output is correct
4 Incorrect 214 ms 211804 KB Output isn't correct
5 Halted 0 ms 0 KB -