oj.uz

Submission #1106915

# Submission time Handle Problem Language Result Execution time Memory
1106915 2024-10-31T09:11:58 Z matu Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 3 ms 1016 KB 
#include <bits/stdc++.h>
// #include <tr2/dynamic_bitset>
 
using namespace std;
// using namespace tr2;
#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const long double eps = 1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randgen(int left, int right) {
    return uniform_int_distribution<int>(left, right)(rng);
}
long long randgenll(long long left, long long right) {
    return uniform_int_distribution<long long>(left, right)(rng);
}
 
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
struct Mint
{
    int val;
    Mint(int x = 0)
    {
        val = x % mod;
    }
    Mint(long long x)
    {
        val = x % mod;
    }
    Mint operator+(Mint oth)
    {
        return val + oth.val;
    }
    Mint operator*(Mint oth)
    {
        return 1LL * val * oth.val;
    }
    Mint operator-(Mint oth)
    {
        return val - oth.val + mod;
    }
    Mint fp(Mint a, long long n){
        Mint p = 1;
        while(n){
            if(n & 1){
                p = p * a;
            }
            a = a * a;
            n /= 2;
        }
        return p;
    }
    Mint operator/(Mint oth){
        Mint invers = fp(oth, mod - 2);
        return 1LL * val * invers.val;
    }
    friend ostream& operator << (ostream& os, const Mint& lol){
        os << lol.val;
        return os;
    }
};
 
struct AINT{
    vector<pair<ll,Mint>> aint;
    vector<pair<ll,Mint>> lazy;
    pair<ll,Mint> b;
    AINT(int n){
        b = {1e18,Mint(0)};
        aint.assign(n * 4 + 1,make_pair(1e18,Mint(0)));
        lazy.assign(n * 4 + 1, make_pair(1e18, Mint(0)));
    }
    void update(int v, int tl, int tr, int l, int r, pair<ll,Mint> val){
        if(lazy[v].first != 1e18){
            if(aint[v].first == lazy[v].first){
                aint[v].second = aint[v].second + lazy[v].second;
            }else if(aint[v].first > lazy[v].first) aint[v] = lazy[v];
 
            if(tl != tr){
                if(lazy[v * 2].first == lazy[v].first){
                    lazy[v * 2].second = lazy[v *  2].second + lazy[v].second;
                }else if(lazy[v * 2].first > lazy[v].first) lazy[v * 2] = lazy[v];
                
 
                if(lazy[v * 2 + 1].first == lazy[v].first){
                    lazy[v * 2 + 1].second = lazy[v * 2 + 1].second + lazy[v].second;
                }else if(lazy[v * 2 + 1].first > lazy[v].first){
                    lazy[v * 2 + 1] = lazy[v];
                }
            }
            lazy[v] = b;
        }
        if(l <= tl && r >= tr){
            if(aint[v].first == val.first){
                aint[v].second = aint[v].second + val.second;
            }else if(aint[v].first > val.first){
                    aint[v] = val;
            }
 
            if(tl != tr){
                if(lazy[v * 2].first == val.first){
                    lazy[v * 2].second = lazy[v *  2].second + val.second;
                }else if(lazy[v * 2].first > val.first){
                    lazy[v * 2] = val;
                }
                
 
                if(lazy[v * 2 + 1].first == val.first){
                    lazy[v * 2 + 1].second = lazy[v * 2 + 1].second + val.second;
                }else if(lazy[v * 2 + 1].first > val.first){
                    lazy[v * 2 + 1] = val;
                }
            }
            return;
        }
        if(l > tr || r < tl) return;
        int tm = (tl + tr) / 2;
        update(v * 2, tl, tm, l,r , val);
        update(v * 2 + 1, tm + 1, tr, l, r, val);
        
        if(aint[v * 2].first == aint[v * 2 + 1].first){
            aint[v] = aint[v * 2];
            aint[v].second = aint[v].second + aint[v * 2 + 1].second;
        }else{
            if(aint[v * 2].first < aint[v * 2 + 1].first) aint[v] = aint[v * 2];
            else aint[v] = aint[v * 2 + 1];
        }
 
 
    }
    pair<ll,Mint> query(int v, int tl, int tr, int l, int r){
        if(lazy[v].first != 1e18){
            if(aint[v].first == lazy[v].first){
                aint[v].second = aint[v].second + lazy[v].second;
            }else if(aint[v].first > lazy[v].first) aint[v] = lazy[v];
 
            if(tl != tr){
                if(lazy[v * 2].first == lazy[v].first){
                    lazy[v * 2].second = lazy[v *  2].second + lazy[v].second;
                }else if(lazy[v * 2].first > lazy[v].first) lazy[v * 2] = lazy[v];
                
 
                if(lazy[v * 2 + 1].first == lazy[v].first){
                    lazy[v * 2 + 1].second = lazy[v * 2 + 1].second + lazy[v].second;
                }else if(lazy[v * 2 + 1].first > lazy[v].first){
                    lazy[v * 2 + 1] = lazy[v];
                }
            }
            lazy[v] = b;
        }
        if(l <= tl && r >= tr) return aint[v];
        if(l > tr || r < tl) return make_pair(1e18,Mint(0));
        int tm = (tl + tr) / 2;
        pair<ll,Mint> p1 = query(v * 2, tl ,tm, l, r);
        pair<ll,Mint> p2 = query(v * 2 + 1, tm + 1, tr, l,r);
        if(p1.first == p2.first){
            p1.second = p1.second + p2.second;
            return p1;
        }else if(p1.first < p2.first) return p1;
        return p2;
 
        // int tm = (tl + tr) / 2;
        // if(l <= tl && r >= tr) return aint[v];
        // if(l > tr || r < tl) return 0;
        // return max(query(v * 2, tl, tm,l,r), query(v * 2 + 1, tm + 1, tr, l,r));
        
    }
};
struct AIB{
    vector<int> aib;
    AIB(int n){
        aib.assign(n + 1,0);
    
    }
    void update(int pos, int val){
        for(; pos < aib.size(); pos += (pos & -pos)){
            aib[pos] += val;
        }
    }
    int query(int pos){
        int pl = 0;
   
        for(; pos > 0; pos -= (pos & -pos)) pl += aib[pos];
        return pl;
    }
};
 
int red = 0;
int ______________________________________________________________________________________________________________________________________________;
 
const int N = 3e4 + 1;
void solve(){
    int n, m;
    cin >> n >> m;
    vector<ll> dp(n + 1,1e18);
    queue<int> q;
    
    vector<bitset<N>> fr(n + 1);
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j += i){
            fr[i][j] = 1;
        }
    }
    bitset<N> barak, obama;
    vector<vector<int>> lol(n + 1);
    int rot = 0, p = 0;
    for(int i = 1; i <= m; i++){
        int pos, c;
        cin >> pos >> c;
        pos++;
        if(c) lol[pos].push_back(c);
        if(i == 1){
            dp[pos] = 0;
            q.push(pos);
        }else if(i == 2){
            rot = pos;
            p = c;
        }
    }
    for(int i = 1; i <= n; i++){
        if(lol.size()){
            set<int> s(lol[i].begin(),lol[i].end());
            lol[i].assign(s.begin(),s.end());
            sort(lol[i].begin(), lol[i].end(), greater<int>());
        }
    }
    while(q.size()){
        int nod = q.front();
        q.pop();
        // cout << nod << " ";
        barak <<= n;
        obama <<= n;
        for(auto i : lol[nod]){
            int cnt = 0;
            if(i >= n) continue;
            barak = (obama ^ fr[i]) & fr[i];
            
            for(int j = 0; j + nod <= n; j = barak._Find_next(j)){
                if(dp[j + nod] > dp[nod] + cnt){
                    dp[j + nod] = dp[nod] + cnt;
                    q.push(j + nod);
                }
                cnt++;
            }

            cnt = 0;
            for(int j = 0; nod - j >= 1; j = barak._Find_next(j)){
                if(dp[nod - j] > dp[nod] + cnt){
                    dp[nod - j] = dp[nod] + cnt;
                    q.push(nod - j);
                }
                cnt++;
            }
            obama |= fr[i];
        }
    }
    if(dp[rot] == 1e18) cout << -1;
    else cout << dp[rot];
    return;

   
}   
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1; 
    if(red) cin >> t;
   
    while(t--){
        solve();
    }
 
 
}
 
 
/*
 
2 2 2 2 4
1 3 5
 
 
1 30
1 40
120 2 
2 430
100 3 
3 30
100 4 
4 490
100 5 
5 440
40 6 
6 290
50 7 
7 190
290 8 
8 430
50 9 
9 60
190 10 
10 490
*/

Compilation message

skyscraper.cpp: In member function 'void AIB::update(int, int)':
skyscraper.cpp:176:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |         for(; pos < aib.size(); pos += (pos & -pos)){
      |               ~~~~^~~~~~~~~~~~
skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:206:18: warning: variable 'p' set but not used [-Wunused-but-set-variable]
  206 |     int rot = 0, p = 0;
      |                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 760 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 3 ms 848 KB Output is correct
12 Correct 1 ms 848 KB Output is correct
13 Correct 1 ms 848 KB Output is correct
14 Incorrect 2 ms 848 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 3 ms 848 KB Output is correct
12 Correct 1 ms 848 KB Output is correct
13 Correct 1 ms 848 KB Output is correct
14 Incorrect 2 ms 1016 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 508 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 3 ms 848 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 848 KB Output is correct
14 Incorrect 2 ms 848 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 2 ms 844 KB Output is correct
11 Correct 3 ms 848 KB Output is correct
12 Correct 1 ms 848 KB Output is correct
13 Correct 1 ms 848 KB Output is correct
14 Incorrect 2 ms 848 KB Output isn't correct
15 Halted 0 ms 0 KB -