Submission #763156

#	Time	Username	Problem	Language	Result	Execution time	Memory
763156		taintedsilk	Garaža (COCI17_garaza)	C++14	160 / 160	531 ms	33124 KiB

garaza

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

struct qhash
{
    static uint64_t splitmix64(uint64_t x)
    {
        // http://x...content-available-to-author-only...i.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x)
        const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

typedef long long ll;
typedef bool bl;
typedef string str;
typedef unsigned long long ull;
typedef double db;

#define fi first
#define se second
#define mp(p1, p2) make_pair(p1, p2)
#define f(i, n) for (ll i = 0; i < n; i += 1)
#define fv(i, v) for (typeof(v.begin()) i = v.begin(); i != v.end(); i++)
#define fu(i, start, end) for (int i = start; i < end; i += 1)
#define fd(i, start, end) for (int i = start; i >= end; i -= 1)
#define BIT(var, pos) ((bool)((var) & (1 << (pos))))
#define pb push_back
#define ordered_set tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update>

#define MOD 111539786
#define vv vector<vector<ll>>
#define pv vector<pair<ll, ll>>
struct noob{
    ll cnt;
    pv pref, suf;
    noob(pv &pref, pv &suf) : pref(pref), suf(suf) {}
    noob (ll a) {
        pref.push_back({a, 1});
        suf.push_back({a, 1});
        cnt = (a != 1);
    }
    noob() {
        cnt = 0;
    }
};
noob combine(noob &a, noob &b){
    noob c(a.pref, b.suf);
    
    f(i, a.suf.size()) {
        if (c.suf.size()) {
            ll val = __gcd<ll>(c.suf.back().fi, a.suf[i].fi);
            if (val == c.suf.back().fi) c.suf.back().se += a.suf[i].se;
            else c.suf.push_back({val, a.suf[i].se});
        }
        else c.suf.push_back(a.suf[i]);
    }
    
    f(i, b.pref.size()) {
        if (c.pref.size())  {
            ll val = __gcd<ll>(c.pref.back().fi, b.pref[i].fi);
            if (val == c.pref.back().fi) c.pref.back().se += b.pref[i].se;
            else c.pref.push_back({val, b.pref[i].se});
        }
        else c.pref.push_back(b.pref[i]);
    }
    c.cnt = b.cnt + a.cnt;
    ll j = b.pref.size() - 1;
    ll sum = 0;
    f(j, b.pref.size()) {
        sum += b.pref[j].se;
    }
    f(i, a.suf.size()) {
        while (j >= 0) {
            ll val = __gcd<ll>(b.pref[j].fi, a.suf[i].fi);
            if (val == 1) {
                sum -= b.pref[j].se;
                j--;
            }
            else break;
        }
        c.cnt += a.suf[i].se * sum;
        
    }
    return c;
}
ll arr[100000], n ,q;
noob st[200002];
void build() {
    fd(i, n - 1, 1) {
        st[i] = combine(st[i << 1], st[i << 1 | 1]);
    }
}
ll query(ll l, ll r) {
    noob resl, resr;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) resl = combine(resl, st[l++]);
        if (r & 1) resr = combine(st[--r], resr);
    }
    return combine(resl, resr).cnt;
}
void update(ll i, ll x) {
    for (st[i += n] = noob(x); i >>= 1;) {
        st[i] = combine(st[i<<1],st[i<<1|1]);
    }
}
void solve() { 
    cin >> n >> q;
    f(i, n) {
        cin >> arr[i];
        st[i + n] = noob(arr[i]);
    }
    build();
    ll a, b, c;
    f(i, q) {
        cin >> a >> b >> c;

        if (a == 1) update(b - 1, c);
        else cout << query(b - 1, c) << '\n';        
    }
    
    
}
int main()
{

    //freopen("SEQUENCE.INP", "r" ,stdin); freopen("SEQUENCE.OUT", "w", stdout);
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    long long test = 1;

    //cin >> test;
    for (int i = 0; i < test; i += 1)
    {
        solve();
    }
    return 0;
}

Compilation message (stderr)

garaza.cpp: In function 'noob combine(noob&, noob&)':
garaza.cpp:35:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 | #define f(i, n) for (ll i = 0; i < n; i += 1)
......
   62 |     f(i, a.suf.size()) {
      |       ~~~~~~~~~~~~~~~             
garaza.cpp:62:5: note: in expansion of macro 'f'
   62 |     f(i, a.suf.size()) {
      |     ^
garaza.cpp:35:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 | #define f(i, n) for (ll i = 0; i < n; i += 1)
......
   71 |     f(i, b.pref.size()) {
      |       ~~~~~~~~~~~~~~~~            
garaza.cpp:71:5: note: in expansion of macro 'f'
   71 |     f(i, b.pref.size()) {
      |     ^
garaza.cpp:35:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 | #define f(i, n) for (ll i = 0; i < n; i += 1)
......
   82 |     f(j, b.pref.size()) {
      |       ~~~~~~~~~~~~~~~~            
garaza.cpp:82:5: note: in expansion of macro 'f'
   82 |     f(j, b.pref.size()) {
      |     ^
garaza.cpp:35:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 | #define f(i, n) for (ll i = 0; i < n; i += 1)
......
   85 |     f(i, a.suf.size()) {
      |       ~~~~~~~~~~~~~~~             
garaza.cpp:85:5: note: in expansion of macro 'f'
   85 |     f(i, a.suf.size()) {
      |     ^

• Subtask 1: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40
• Subtask 4: 40 / 40