oj.uz

Submission #668261

# Submission time Handle Problem Language Result Execution time Memory
668261 2022-12-03T12:31:28 Z ktkerem Toll (BOI17_toll) C++17
7 / 100
 127 ms 29092 KB 
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
/**/
//typedef int ll;
typedef long long ll;
typedef unsigned long long ull;
typedef std::string str;
//typedef vector<std::vector<ll>> vv; 
/*typedef __int128 vll;
typedef unsigned __int128 uvll;*/
#define llll std::pair<ll , ll>
#define pb push_back
#define pf push_front
#define halo cout << "hello\n"
#define fi first
#define sec second
#define vv(x) std::vector<std::vector<x>>
#define all(a) a.begin() , a.end()
const ll limit = 1e15+7; 
const ll ous = 3e5 + 7;
const ll dx[4] = {-1 , 0 , 1 , 0} , dy[4] = {0,1,0,-1};
ll n , m , k , o;
std::vector<std::vector<std::vector<ll>>> valt , ar;
std::vector<std::vector<ll>> mult(std::vector<std::vector<ll>> a , std::vector<std::vector<ll>> b){
    std::vector<std::vector<ll>> res(a.size() , std::vector<ll>(b.size() , limit));
    for(ll i = 0;k>i;i++){
        for(ll j = 0;k>j;j++){
            ll cur = limit;
            for(ll tt =0;k>tt;tt++){
                cur = std::min(cur , a[i][tt] + b[tt][j]);
            }
            res[i][j] = cur;
        }
    }
    return res;
}
void build(ll l , ll r , ll a){
    if(l == r){
        valt[a] = ar[l];
        return;
    }
    ll md = (l + r)/2;
    build(l , md , a*2);
    build(md+1 , r , a*2+1);
    valt[a] = mult(valt[a*2] , valt[a*2+1]);
    return;
}
std::vector<std::vector<ll>> rq(ll l , ll r , ll nl , ll nr , ll a){
    if(nl > r || nr < l){
        std::vector<std::vector<ll>> rte(k , std::vector<ll>(k , limit));
        for(ll i = 0;k>i;i++){
            rte[i][i] = 0;
        }
        return rte;
    }
    if(l <= nl && r >= nr){
        return valt[a];
    }
    ll md = (nl + nr)/2;
    std::vector<std::vector<ll>> f = rq(l , r , nl , md , a*2) , s = rq(l , r , md+1 , nr , a*2+1);
    return mult(f , s);
}
void solve(){
    std::cin >> k >> n >> m >> o;
    ar.resize(n/k+1 , std::vector<std::vector<ll>>(k , std::vector<ll>(k , limit)));
    valt.resize((n/k+1) * 3 , std::vector<std::vector<ll>>(k , std::vector<ll>(k , limit)));
    for(ll i = 0;m>i;i++){
        ll x , y , z;std::cin >> x >> y >> z;
        ar[x/k][x%k][y%k] = std::min(ar[x/k][x%k][y%k] , z);
    }
    /*for(ll i = 0;n/k>=i;i++){
        for(ll j = 0;k>j;j++){
            for(ll tso = 0;k>tso;tso++){
                std::cout << ar[i][j][tso] << " ";
            }
            std::cout << "\n";
        }
        std::cout << "\n";
    }*/
    build(0 , (n-1)/k , 1);
    while(o--){
        ll x , y;std::cin >> x >> y;
        if(x/k >= y/k){
            std::cout << -1 << "\n";
        }
        else{
            std::vector<std::vector<ll>> bt = rq(x/k , y/k - 1 , 0 , (n-1)/k , 1);
            /*for(ll j = 0;k>j;j++){
                for(ll tso = 0;k>tso;tso++){
                    std::cout << bt[j][tso] << " ";
                }
                std::cout << "\n";
            }*/
            if(bt[x%k][y%k] < limit){
                std::cout << bt[x%k][y%k] << "\n"; 
            }
            else{
                std::cout << -1 << "\n";
            }
        }
    }
    return;/**/
}
signed main(){
    std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
    ll t=1;
    //std::cin >> t;
    ll o = 1;
    while(t--){ 
        //cout << "Case " << o++ << ":\n";
        solve();
    }
    return 0;
}/**/

Compilation message

toll.cpp:5:78: warning: "/*" within comment [-Wcomment]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
      |                                                                               
toll.cpp: In function 'int main()':
toll.cpp:112:8: warning: unused variable 'o' [-Wunused-variable]
  112 |     ll o = 1;
      |        ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 18696 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 6 ms 596 KB Output is correct
7 Correct 6 ms 588 KB Output is correct
8 Correct 122 ms 18476 KB Output is correct
9 Correct 118 ms 18428 KB Output is correct
10 Correct 110 ms 17672 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 16796 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 316 KB Output is correct
7 Correct 26 ms 736 KB Output is correct
8 Correct 36 ms 760 KB Output is correct
9 Correct 93 ms 18428 KB Output is correct
10 Runtime error 62 ms 29072 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 3 ms 688 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 48 ms 18220 KB Output is correct
11 Correct 66 ms 16708 KB Output is correct
12 Runtime error 74 ms 29092 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 3 ms 688 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 48 ms 18220 KB Output is correct
11 Correct 66 ms 16708 KB Output is correct
12 Runtime error 74 ms 29092 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 18696 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 6 ms 596 KB Output is correct
7 Correct 6 ms 588 KB Output is correct
8 Correct 122 ms 18476 KB Output is correct
9 Correct 118 ms 18428 KB Output is correct
10 Correct 110 ms 17672 KB Output is correct
11 Correct 108 ms 16796 KB Output is correct
12 Correct 0 ms 316 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 316 KB Output is correct
17 Correct 26 ms 736 KB Output is correct
18 Correct 36 ms 760 KB Output is correct
19 Correct 93 ms 18428 KB Output is correct
20 Runtime error 62 ms 29072 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -