oj.uz

Submission #682345

# Submission time Handle Problem Language Result Execution time Memory
682345 2023-01-16T06:57:38 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 1341 ms 24156 KB 
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

#define int long long
#define ll long long
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define freopen(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

const int N = 250000 + 5;
const int M = 1e3 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e17;

int n, k, x[N], y[N], id[N], cc;
vector<pair<int, int>> v;

int dist(int i, int j){
    return abs(x[i] - x[j]) + abs(y[i] - y[j]);
}

int convert(int i, int j){
    if(i < j) swap(i, j);
    return i * (n + 1) + j;
}

multiset<int> st;

void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        v.pb({x[i], y[i]});
    }
    sort(all(v));
    cc = 50000000 / n;
    for(int i = 1; i <= n; i++){
        x[i] = v[i - 1].F;
        y[i] = v[i - 1].S;
        for(int j = max(1ll, i - cc); j < i; j++){
            if(st.size() < k){
                st.insert(dist(i, j));    
            }else{
                auto to = st.end();
                to--;
                if(*to > dist(i, j)){
                    st.erase(to);
                    st.insert(dist(i, j));
                }
            }
            
        }
    }
    while(k--){
        cout << *(st.begin()) << '\n';
        st.erase(st.begin());
    }

    //N * log() * const
}

main() {
    fast
    int tt = 1;
    // cin >> tt;
    while(tt--){
        solve();
    }
}

Compilation message

road_construction.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("O3")
      | 
road_construction.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization("unroll-loops")
      | 
road_construction.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:200000000")
      | 
road_construction.cpp: In function 'void solve()':
road_construction.cpp:51:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   51 |             if(st.size() < k){
      |                ~~~~~~~~~~^~~
road_construction.cpp: At global scope:
road_construction.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 14680 KB Output is correct
2 Correct 210 ms 14628 KB Output is correct
3 Correct 168 ms 14676 KB Output is correct
4 Correct 148 ms 14688 KB Output is correct
5 Correct 211 ms 13500 KB Output is correct
6 Correct 5 ms 468 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1277 ms 21172 KB Output is correct
2 Correct 1246 ms 24156 KB Output is correct
3 Correct 133 ms 14592 KB Output is correct
4 Incorrect 933 ms 23948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 8216 KB Output is correct
2 Correct 251 ms 9328 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 190 ms 8284 KB Output is correct
5 Correct 211 ms 8688 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 8216 KB Output is correct
2 Correct 251 ms 9328 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 190 ms 8284 KB Output is correct
5 Correct 211 ms 8688 KB Output is correct
6 Correct 206 ms 8236 KB Output is correct
7 Correct 212 ms 9484 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 210 ms 10292 KB Output is correct
11 Correct 197 ms 8336 KB Output is correct
12 Correct 223 ms 10604 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 14680 KB Output is correct
2 Correct 210 ms 14628 KB Output is correct
3 Correct 168 ms 14676 KB Output is correct
4 Correct 148 ms 14688 KB Output is correct
5 Correct 211 ms 13500 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Incorrect 1341 ms 17132 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 14680 KB Output is correct
2 Correct 210 ms 14628 KB Output is correct
3 Correct 168 ms 14676 KB Output is correct
4 Correct 148 ms 14688 KB Output is correct
5 Correct 211 ms 13500 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 1277 ms 21172 KB Output is correct
8 Correct 1246 ms 24156 KB Output is correct
9 Correct 133 ms 14592 KB Output is correct
10 Incorrect 933 ms 23948 KB Output isn't correct
11 Halted 0 ms 0 KB -