Submission #1101846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101846		underwaterkillerwhale	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	2 ms	2552 KiB

diameter

//#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e6 + 7;
int Mod = 998244353;///lon
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 450;

int n, T, P;
int a[N], b[N];

int cnt[2 * N];
vector<vector<int>> vec;

int Ans[N], pw[N];

void solution () {
    cin >> n >> P;

    int P2 = P + 1;
    vec.resize(2 * P + 1);

    rep (i, 1, n) cin >> a[i];
    rep (i, 1, n) cin >> b[i];

    pw[1] = n;
    rep (i, 2, n) pw[i] = 1LL * pw[i - 1] * n % Mod;

    auto calc =  [] () {
        rep (i, 1, n) {
            cnt[a[i] + P]++;
            vec[a[i] + b[i]].pb(i);
        }
        int larger = 0;
        reb (i, 2 * P, 1) {
            iter (&id, vec[i]) {
                Ans[id] = 1 + larger - (b[id] < P ? 1 : 0);
            }
            larger += cnt[i];
            vector<int> ().swap(vec[i]);
            cnt[i] = 0;
        }
        int res = 0;
        rep (i, 1, n) {
            res += 1LL * Ans[i] * pw[i] % Mod;
            if (res >= Mod) res -= Mod;
        }
        return res;
    };

    cout << calc() <<"\n";

    cin >> T;
    rep (i, 1, T) {
        ll af, bf, cf, as, bs, cs;
        cin >> af >> bf >> cf >> as >> bs >> cs;
        rep (i, 1, n) {
            a[i] = (af * a[i] % P2 * a[i] % P2 + bf * a[i] % P2 * i % P2 + cf * i % P2 * i % P2) % P2;
            b[i] = (as * b[i] % P2 * b[i] % P2 + bs * b[i] % P2 * i % P2 + cs * i % P2 * i % P2) % P2;
        }
        cout << calc() <<"\n";
    }
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
    file("SRANK");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +10

5 5
01101
10001
00110
10101
00100
*/

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:84:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 | #define file(name) freopen(name".inp","r",stdin); \
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:87:5: note: in expansion of macro 'file'
   87 |     file("SRANK");
      |     ^~~~
diameter.cpp:85:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 | freopen(name".out","w",stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:87:5: note: in expansion of macro 'file'
   87 |     file("SRANK");
      |     ^~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27