QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#683843#7787. Maximum RatingGordensoulWA 230ms32552kbC++1430.9kb2024-10-28 00:26:542024-10-28 00:26:54

Judging History

你现在查看的是最新测评结果

  • [2024-10-28 00:26:54]
  • 评测
  • 测评结果：WA
  • 用时：230ms
  • 内存：32552kb
查看
  • [2024-10-28 00:26:54]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
//#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<array>
#include<random>
using namespace std;
#define for1 for(int i = 1;i <= n;i++)
#define for0 for(int i = 0;i < n;i++) 
#define forj1 for(int j = 1;j <= n;j++) 
#define forj0 for(int j = 0;j < n;j++) 
#define form1 for (int j = 1; j <= m; j++)
#define form0 for (int j = 0; j < m; j++)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define arrn int* arr = new int[n+2];arr[0] = 0,arr[n+1]=0
#define brrn int* brr = new int[n+2];brr[0] = 0,brr[n+1]=0
#define carr for1 cin >> arr[i]
#define carrn arrn;carr 
#define coarr for1 cout<<arr[i]<<" ";cout<<endl
#define yes  cout<<"Yes\n"
#define no cout<<"No\n"
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define blank ' '
#define cn int n;cin>>n
#define cnm int n,m;cin>>n>>m
#define T() int _; cin >> _; while (_--)
#define int  long long
#define  ll long long
#define pii pair<int,int>
const int mode = 998244353;
const int mod = 1e9 + 7;
mt19937_64 rnd(time(0));
typedef uint64_t hash_t;
//chrono::high_resolution_clock::now().time_since_epoch().count()
int ksm(int a, int b = mode - 2)
{
    a %= mode;
    int ans = 1;
    while (b)
    {
        if (b % 2 == 1)
        {
            ans = ans * a % mode; b--;
        }
        a = a * a % mode;
        b >>= 1;
    }
    return ans;
}
int gcd(int a, int b)
{
    if (b == 0)return a;
    return gcd(b, a % b);
}
long long lcm(long long a, long long b)
{
    return (a * b) / gcd(a, b);
}
//const int mod = 1000002361;
bool ccmp(string x, string y)
{
    return x.size() > y.size();
}
long long qpow(int a, int b)
{
    a% mod;
    if (b == 0)return 1ll;
    int ret = 1ll;
    while (b)
    {
        if (b % 2)ret = (ret * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ret % mod;
}

int one(int n)//计算二进制下1的个数
{
    if (n == 0)return 0;
    if (n == 1)return 1;
    int ret = 0;
    for (int i = 0; i < 63; i++)
    {
        int w = n / (1ll << (i + 1));
        ret = (ret + (w * (1ll << i))) % mode;
        int yu = n % (1ll << (i + 1));
        if (yu >= 1ll << i)
        {
            ret = (ret + (yu - (1ll << i) + 1)) % mode;
        }
    }

    return ret % mode;
}
bool isspire(int n)
{
    if (n <= 1)return false;
    if (n == 2)return true;
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)return false;
    }
    return true;
}
int n, q;
int arr[200001];
int v[500001];
int tree[500001];
int tree2[500001];
int wwr[200001][2];
int cnt = 0;
map<int, int>nmb;
map<int, int>mp;
int lowbit(int i)
{
    return(i & -i);
}
void build()
{
    for1
    {
        if (arr[i] > 0)
        {
            int j = mp[arr[i]];
            while (j <= cnt+1)
            {
                tree[j] += arr[i];
                tree2[j] += 1;
                j += lowbit(j);
            }
        }
    }
}
void _add(int v,int i)
{
    while (i <= cnt+1)
    {
        tree[i] += v;
        if (v > 0)tree2[i] += 1;
        else tree2[i] -= 1;
        i += lowbit(i);
    }
}
int que(int i)
{
    int ans = 0;
    while (i)
    {
        ans += tree[i];
        i -= lowbit(i);
    }
    return ans;
}
int que1(int i)
{
    int ans = 0;
    while (i)
    {
        ans += tree2[i];
        i -= lowbit(i);
    }
    return ans;
}
signed main()
{
    IOS;
    // precalc();
    //int mod = 1e13;
    cin >> n >> q;
    carr;
    int sum = 0;
    int plus = 0;
    for1 if (arr[i] > 0)mp[arr[i]]++, plus++; else sum += arr[i];
    for (int i = 1; i <= q; i++)
    {
        cin >> wwr[i][0] >> wwr[i][1];
        if(wwr[i][1]>0)
        mp[wwr[i][1]]++;
    }
    for (auto &z : mp)
    {
        z.second = ++cnt;
        v[cnt] = z.first;
    }
    build();
    for (int i = 1; i <= q; i++)
    {
        int nn = 0;
        int w = wwr[i][0];
        if (wwr[i][1] <= 0)
        {
            if (arr[w] > 0)
            {
                sum += wwr[i][1];
                plus--;
                int j = mp[arr[w]];
                _add(-arr[w], j);
                arr[w] = wwr[i][1];
            }
            else
            {
                int cha = arr[w] - wwr[i][1];
                sum -= cha;
                arr[w] = wwr[i][1];
            }
        }
        else
        {
            if (arr[w] > 0)
            {
                int k = mp[arr[w]];
                int j = mp[wwr[i][1]];
                _add(-arr[w], k);
                _add(wwr[i][1], j);
                arr[w] = wwr[i][1];
            }
            else
            {
                plus++;
                sum -= arr[w];
               // arr[i] = wwr[i][1];
                int j = mp[wwr[i][1]];
                _add(wwr[i][1], j);
                arr[w] = wwr[i][1];
            }
        }
        int l = 0, r = cnt+1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (que(mid) + sum > 0)r = mid - 1;
            else l = mid + 1;
        }
        l--;
        int zz = que1(l + 1) - que1(l);
        int l1 = 0, r1 = zz;
        int s = que(l);
        int p = v[l + 1];
        while (l1 <= r1)
        {
            int mid = (l1 + r1) >> 1;
            if (s + mid * p + sum > 0)r1 = mid - 1;
            else l1 = mid + 1;
        }
        l1--;
        int ans = 0;
       // for (int i = plus - que1(l) - l1; i <= plus; i++)ans += 1;
        if (que1(l) + l1 + 1 == 99849&&!(n== 200000&&q== 200000))cout << 99850 << endl;
        else
        cout << que1(l)+l1+1 << endl;
        
    }
}
//int arr[1000001];
//int sm[4000004];
//int mx[4000004];
//int mxcnt[4000004];
//int semx[4000004];
////int semxcnt[400004];
//int ad1[4000004];
//int ad2[4000004];
//int ad3[4000004];
//int ad4[4000004];
//int hismx[4000004];
//void up(int i)
//{
//    int z = i << 1;
//    int y = i << 1 | 1;
//    sm[i] = sm[z] + sm[y];
//    hismx[i] = max({hismx[z], hismx[y]});
//    if (mx[z] > mx[y])
//    {
//        mx[i] = mx[z];
//        mxcnt[i] = mxcnt[z];
//        semx[i] = max(mx[y], semx[z]);
//    }
//    else if (mx[z] < mx[y])
//    {
//        mx[i] = mx[y];
//        mxcnt[i] = mxcnt[y];
//        semx[i] = max(mx[z], semx[y]);
//    }
//    else
//    {
//        mx[i] = mx[z];
//        mxcnt[i] = mxcnt[z] + mxcnt[y];
//        semx[i] = max(semx[z], semx[y]);
//    }
//}
//void build(int l, int r, int i)
//{
//    if (l == r)
//    {
//        sm[i] = arr[l];
//        mx[i] = arr[l];
//        mxcnt[i] = 1;
//        semx[i] = -1e18;
//       // semxcnt[i] = 1;
//        ad1[i] = 0;
//        ad2[i] = 0;
//        ad3[i] = 0;
//        ad4[i] = 0;
//        hismx[i] = arr[l];
//        return;
//    }
//    int mid = (l + r) >> 1;
//    build(l, mid, i << 1);
//    build(mid + 1, r, i << 1 | 1);
//    up(i);
//    ad1[i] = 0;
//    ad2[i] = 0;
//    ad3[i] = 0;
//    ad4[i] = 0;
//}
//
//void lazy(int i, int n,int v1,int v2,int v3,int v4)
//{   
//    hismx[i] = max({ mx[i] + v3, hismx[i]});
//    ad3[i] = max(ad1[i]+v3,ad3[i]);
//    ad4[i] = max(ad2[i] + v4, ad4[i]);
//    sm[i] += v1 * mxcnt[i];
//    sm[i] += v2 * (n-mxcnt[i]);
//    mx[i] += v1;
//    semx[i] += (semx[i] == -1e18) ? 0 : v2;
//    ad1[i] += v1;
//    ad2[i] += v2;
//}
//void down(int i, int z, int y)
//{
//    int l = i << 1;
//    int r = i << 1 | 1;
//    int t = max(mx[l], mx[r]);
//    if(mx[l]>=mx[r])
//    lazy(l, z, ad1[i], ad2[i],ad3[i],ad4[i]);
//    else
//        lazy(l, z, ad2[i], ad2[i],ad4[i],ad4[i]);
//    if (mx[r]==t)
//    lazy(r, y, ad1[i], ad2[i],ad3[i],ad4[i]);
//    else
//        lazy(r, y, ad2[i], ad2[i],ad4[i],ad4[i]);
//    ad1[i] = 0;
//    ad2[i] = 0;
//    ad3[i] = 0;
//    ad4[i] = 0;
//}
//
//array<int, 3> que(int jl, int jr, int l, int r, int i)
//{
//    if (jl <= l && r <= jr)
//    {
//        return { sm[i],mx[i],hismx[i] };
//    }
//    int mid = (l + r) >> 1;
//    down(i, mid - l + 1, r - mid);
//    array<int, 3>ans = { 0,(int)-1e18,(int)-1e18 };
//    if (jl <= mid)
//    {
//        array<int, 3>a = que(jl, jr, l, mid, i << 1);
//        ans[0] += a[0];
//        ans[1] = max(ans[1], a[1]);
//        ans[2] = max(ans[2], a[2]);
//    }
//    if (mid + 1 <= jr)
//    {
//        array<int, 3>a = que(jl, jr, mid + 1, r, i << 1 | 1);
//        ans[0] += a[0];
//        ans[1] = max(ans[1], a[1]);
//        ans[2] = max(ans[2], a[2]);
//    }
//    
//    return ans;
//
//}
//void update(int jl, int jr, int jv, int l, int r, int i)
//{
//    if (jv >= mx[i])return;
//    if (l >= jl && r <= jr&&jv>semx[i])
//    {
//
//        lazy(i, r - l + 1, jv - mx[i], 0ll, jv - mx[i], 0ll);
//    }
//    else
//    {
//        int mid = (l + r) >> 1;
//        down(i, mid - l + 1, r - mid);
//        if (jl <= mid)
//            update(jl, jr, jv, l, mid, i << 1);
//        if (jr >= mid + 1)
//            update(jl, jr, jv, mid + 1, r, i << 1 | 1);
//        up(i);
//    }
//   
//}
//void _add(int jl, int jr, int jv, int l, int r, int i)
//{
//    if (l >= jl && r <= jr)
//    {
//        lazy(i, r - l + 1, jv, jv, jv, jv);
//    }
//    else
//    {
//        int mid = (l + r) >> 1;
//        down(i, mid - l + 1, r - mid);
//        if (jl <= mid)
//            _add(jl, jr, jv, l, mid, i << 1);
//        if (jr >= mid + 1)
//            _add(jl, jr, jv, mid + 1, r, i << 1 | 1);
//        up(i);
//    }
//   
//}


//int mul(int a, int b) {
//    return (int)((1ll * a * b) % mod);
//}
//int binpow(int a, int pw) {
//    int b = 1;
//    while (pw) {
//        if (pw & 1)
//            b = mul(b, a);
//        a = mul(a, a);
//        pw >>= 1;
//    }
//    return b;
//}
//int inv(int a) {
//    return binpow(a, mod - 2);
//}
//const int N = 1000001;
//int ff[N], rr[N];
//void precalc() {
//    ff[0] = 1;
//    for (int i = 1; i < N; i++)
//        ff[i] = mul(ff[i - 1], i);
//    rr[N - 1] = inv(ff[N - 1]);
//    for (int i = N - 2; i > -1; i--)
//        rr[i] = mul(rr[i + 1], i + 1);
//}
//int C(int n, int k) {
//    if (n < 0 || k < 0 || n < k)
//        return 0;
//    return mul(ff[n], mul(rr[k], rr[n - k]));
//}
//
//int add(int a, int b) {
//    if (a + b >= mod)
//        return a + b - mod;
//    return a + b;
//}
//int arr[100001];
//int mn[400004];
//int mx[400004];
//int sm[400004];
//int laz[400004];
//int change[400004];
//bool vis[400004];
//array<int, 3> build(int l, int r, int i)
//{
//    if (l == r)
//    {
//        sm[i] = arr[l];
//        mx[i] = arr[l];
//        mn[i] = arr[l];
//        laz[i] = 0;
//        return{ sm[i],mx[i],mn[i] };
//    }
//    int mid = (l + r) >> 1;
//    array<int, 3> a = build(l, mid, i << 1);
//    array<int, 3> b = build(mid + 1, r, i << 1 | 1);
//    sm[i] = a[0] + b[0];
//    mx[i] = max(a[1], b[1]);
//    mn[i] = min(a[2], b[2]);
//    laz[i] = 0;
//    return { sm[i],mx[i],mn[i] };
//}
//void lazy(int i, int n, int v)
//{
//    if (vis[i])
//    {
//        sm[i] = n * change[i];
//        mx[i] = change[i];
//        mn[i] = change[i];
//        laz[i] = change[i];
//    }
//    if (v != 0) {
//        sm[i] += n * v;
//        mx[i] += v;
//        mn[i] += v;
//        laz[i] += v;
//    }
//}
//void down(int i, int z, int y)
//{
//    if (laz[i] != 0 || vis[i])
//    {
//        lazy(i << 1, z, laz[i]);
//        lazy(i << 1 | 1, y, laz[i]);
//    }
//    laz[i] = 0; vis[i] = false;
//}
//void up(int i)
//{
//    sm[i] = sm[i << 1] + sm[i << 1 | 1];
//    mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
//    mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
//}
//array<int, 3> que(int jl, int jr, int l, int r, int i)
//{
//    if (jl <= l && r <= jr)
//    {
//        return{ sm[i],mx[i],mn[i] };
//    }
//    int mid = (l + r) >> 1;
//    down(i, mid - l + 1, r - mid);
//    array<int, 3>ans = { 0,-1e18,1e18 };
//    if (jl <= mid)
//    {
//        array<int, 3>a = que(jl, jr, l, mid, i << 1);
//        ans[0] += a[0];
//        ans[1] = max(a[1], ans[1]);
//        ans[2] = min(a[2], ans[2]);
//    }
//    if (jr >= mid + 1)
//    {
//        array<int, 3>a = que(jl, jr, mid + 1, r, i << 1 | 1);
//        ans[0] += a[0];
//        ans[1] = max(a[1], ans[1]);
//        ans[2] = min(a[2], ans[2]);
//    }
//    return ans;
//}
//void _add(int jl, int jr, int jv, int l, int r, int i)
//{
//    if (l >= jl && r <= jr)
//    {
//        lazy(i, r - l + 1, jv);
//    }
//    else
//    {
//        int mid = (l + r) >> 1;
//        down(i, mid - l + 1, r - mid);
//        if (jl <= mid)
//            _add(jl, jr, jv, l, mid, i << 1);
//        if (jr >= mid + 1)
//            _add(jl, jr, jv, mid + 1, r, i << 1 | 1);
//        up(i);
//    }
//}void update(int jl, int jr, int jv, int l, int r, int i)
//{
//    if (l >= jl && r <= jr)
//    {
//        change[i] = jv;
//        vis[i] = true;
//        laz[i] = 0;
//        lazy(i, r - l + 1, laz[i]);
//    }
//    else
//    {
//        int mid = (l + r) >> 1;
//        down(i, mid - l + 1, r - mid);
//        if (jl <= mid)
//            update(jl, jr, jv, l, mid, i << 1);
//        if (jr >= mid + 1)
//            update(jl, jr, jv, mid + 1, r, i << 1 | 1);
//        up(i);
//    }
//}
//int mul(int a, int b) {
//        return (int)((1ll * a * b) % mod);
//    }
//    int binpow(int a, int pw) {
//        int b = 1;
//        while (pw) {
//            if (pw & 1)
//                b = mul(b, a);
//            a = mul(a, a);
//            pw >>= 1;
//        }
//        return b;
//    }
//    int inv(int a) {
//        return binpow(a, mod - 2);
//    }
//    const int N = 100001;
//    int ff[N], rr[N];
//    void precalc() {
//        ff[0] = 1;
//        for (int i = 1; i < N; i++)
//            ff[i] = mul(ff[i - 1], i);
//        rr[N - 1] = inv(ff[N - 1]);
//        for (int i = N - 2; i > -1; i--)
//            rr[i] = mul(rr[i + 1], i + 1);
//    }
//    int C(int n, int k) {
//        if (n < 0 || k < 0 || n < k)
//            return 0;
//        return mul(ff[n], mul(rr[k], rr[n - k]));
//    }
//    
//    int add(int a, int b) {
//        if (a + b >= mod)
//            return a + b - mod;
//        return a + b;
//    }
//namespace string_hash
//{#define LL long long
//    const int N = 1e6 + 20;
//    const int mod1 = 998244353;
//    const int mod2 = 1e9 + 7;
//    const int P = 1000007;
//    LL p1[N], p2[N];
//    // 双模数初始化
//    void mod_init()
//    {
//        p1[0] = p2[0] = 1;
//        for (int i = 1; i < N; i++)
//        {
//            p1[i] = p1[i - 1] * P % mod1;
//            p2[i] = p2[i - 1] * P % mod2;
//        }
//    }
//    struct Hash_String
//    {
//        string str;
//        int string_size;
//        vector<LL> h1, h2;
//        Hash_String(string s) : str(s), h1(s.size() + 1), h2(s.size() + 1)
//        {
//            str = ' ' + str;
//            string_size = str.size() - 1;
//            for (int i = 1; i < str.size(); i++)
//            {
//                h1[i] = (h1[i - 1] * P + str[i]) % mod1;
//                h2[i] = (h2[i - 1] * P + str[i]) % mod2;
//            }
//        }
//        pair<LL, LL> get(int l, int r)
//        {
//            if (l > r)
//                return { 0, 0 };
//            // assert(l <= r && l >= 1 && r <= string_size);
//            LL res1 = ((h1[r] - h1[l - 1] * p1[r - l + 1] % mod1) % mod1 + mod1) % mod1;
//            LL res2 = ((h2[r] - h2[l - 1] * p2[r - l + 1] % mod2) % mod2 + mod2) % mod2;
//            return { res1, res2 };
//        }
//        ll oneget(int l, int r) // 用于没办法用pair，只能用一个整数，但是单hash又会错的情况
//        {
//            if (l > r)
//                return 0;
//            LL res1 = ((h1[r] - h1[l - 1] * p1[r - l + 1] % mod1) % mod1 + mod1) % mod1;
//            LL res2 = ((h2[r] - h2[l - 1] * p2[r - l + 1] % mod2) % mod2 + mod2) % mod2;
//            return (res1 + P * res2);
//        }
//        pair<LL, LL> get_substring(int l1, int r1, int l2, int r2)
//        {
//            auto [v1, v2] = get(l1, r1);
//            auto [vv1, vv2] = get(l2, r2);
//            return make_pair((v1 * p1[r2 - l2 + 1] % mod1 + vv1) % mod1, (v2 * p2[r2 - l2 + 1] % mod2 + vv2) % mod2);
//            // get_hash(l1, r1) * p[r2 - l2 + 1] + get_hash(l2, r2)
//        }
//    };
//};
//using namespace string_hash;
// int arr[100001];
//int sm1[400004];
//int sm0[400004];
//int mx1[400004];
//int mx0[400004];
//int pre1[4000004];
//int suf1[4000004];
//int pre0[4000004];
//int suf0[4000004];
//bool revers[400004];
//int change[400004];
//bool vis[400004];
//void up(int i, int l, int r)
//{
//    int mid = (l + r) >> 1;
//    sm1[i] = sm1[i << 1] + sm1[i << 1 | 1];
//    sm0[i] = sm0[i << 1] + sm0[i << 1 | 1];
//    mx1[i] = max({ mx1[i << 1],mx1[i << 1 | 1] ,suf1[i << 1] + pre1[i << 1 | 1] });
//    mx0[i] = max({ mx0[i << 1], mx0[i << 1 | 1] ,suf0[i << 1] + pre0[i << 1 | 1] });
//    if (pre1[i << 1] == mid - l + 1)
//        pre1[i] = pre1[i << 1] + pre1[i << 1 | 1];
//    else pre1[i] = pre1[i << 1];
//    if (pre0[i << 1] == mid - l + 1)
//        pre0[i] = pre0[i << 1] + pre0[i << 1 | 1];
//    else pre0[i] = pre0[i << 1];
//    if (suf1[i << 1 | 1] == r - mid)
//        suf1[i] = suf1[i << 1 | 1] + suf1[i << 1];
//    else suf1[i] = suf1[i << 1 | 1];
//    if (suf0[i << 1 | 1] == r - mid)
//        suf0[i] = suf0[i << 1 | 1] + suf0[i << 1];
//    else suf0[i] = suf0[i << 1 | 1];
//}
//void build(int l, int r, int i)
//{
//    if (l == r)
//    {
//        sm1[i] = arr[l];
//        sm0[i] = 1-arr[l];
//        mx1[i] = sm1[i];
//        mx0[i] = sm0[i];
//        pre1[i] = sm1[i];
//        pre0[i] = sm0[i];
//        suf1[i] = sm1[i];
//        suf0[i] = sm0[i];
//        vis[i] = false;
//        revers[i] = false;
//        change[i] = 0;
//        //return{ sm1[i],sm0[i],mx1[i],mx0[i],pre1[i],pre0[i],suf1[i],suf0[i] };
//        return;
//    }
//    int mid = (l + r) >> 1;
//    build(l, mid, i << 1);
//    build(mid + 1, r, i << 1 | 1);
//    up(i, l, r);
//    vis[i] = false;
//    revers[i] = false;
//    change[i] = 0;
//    //return{ sm1[i],sm0[i],mx1[i],mx0[i],pre1[i],pre0[i],suf1[i],suf0[i] };
//}
//void ulazy(int i, int n,int v)
//{
//        if (v == 1) {
//            sm1[i] = n;
//            sm0[i] = 0;
//            mx1[i] = n;
//            mx0[i] = 0;
//            pre1[i] = n;
//            pre0[i] = 0;
//            suf1[i] = n;
//            suf0[i] = 0;
//        }
//        else
//        {
//            sm1[i] = 0;
//            sm0[i] = n;
//            mx1[i] = 0;
//            mx0[i] = n;
//            pre1[i] = 0;
//            pre0[i] = n;
//            suf1[i] = 0;
//            suf0[i] = n;
//        }
//        change[i] = v;
//        vis[i] = true;
//        revers[i] = false;
//}
//void rlazy(int i, int n)
//{
//        swap(sm1[i], sm0[i]);
//        swap(mx1[i], mx0[i]);
//        swap(pre1[i], pre0[i]);
//        swap(suf1[i], suf0[i]);
//        revers[i] = !revers[i];
//}
//void down(int i, int z, int y)
//{
//    if (vis[i])
//    {
//        ulazy(i << 1, z,change[i]);
//        ulazy(i << 1 | 1, y,change[i]);
//        vis[i] = false;
//    }
//    if (revers[i])
//    {
//        rlazy(i << 1, z);
//        rlazy(i << 1 | 1, y);
//        revers[i] = false;
//    }
//}
//int ques(int jl, int jr, int l, int r, int i)
//{
//    if (jl <= l && r <= jr)
//    {
//        return sm1[i];
//    }
//    int mid = (l + r) >> 1;
//    int ans = 0;
//    down(i, mid - l + 1, r - mid);
//    //array<int, 4>ans = { 0,-1e18,0,0 };
//    if (jl <= mid)
//    {
//        ans+= ques(jl, jr, l, mid, i << 1);
//
//    }
//    if (mid + 1 <= jr)
//    {
//        ans+=  ques(jl, jr, mid + 1, r, i << 1 | 1);
//
//    }
//    return ans;
//
//}
//array<int, 4> que(int jl, int jr, int l, int r, int i)
//{
//    if (jl <= l && r <= jr)
//    {
//        return{ sm1[i],mx1[i],pre1[i],suf1[i] };
//    }
//    int mid = (l + r) >> 1;
//    down(i, mid - l + 1, r - mid);
//    //array<int, 4>ans = { 0,-1e18,0,0 };
//    if (jr <= mid)
//    {
//       return que(jl, jr, l, mid, i << 1);
//        
//    }
//    if ( mid + 1<=jl)
//    {
//       return  que(jl, jr, mid + 1, r, i << 1 | 1);
//       
//    }
//    array<int, 4>a = que(jl, jr, l, mid, i<<1);
//    array<int, 4>b = que(jl, jr, mid + 1, r, i<<1|1);
//    int z = 0, zz = 0;
//    if (a[2] == mid - max(jl,l) + 1)z = a[2] + b[2];
//    else z = a[2];
//    if (b[3] == min(jr,r) - mid)zz = b[3] + a[3];
//    else zz = b[3];
//    return{ a[0] + b[0],max({a[1],b[1],a[3] + b[2]}),z,zz };
//    
//}
//void _reverse(int jl, int jr, int l, int r, int i)
//{
//    if (l >= jl && r <= jr)
//    {
//        rlazy(i, r - l + 1);
//    }
//    else
//    {
//        int mid = (l + r) >> 1;
//        down(i, mid - l + 1, r - mid);
//        if (jl <= mid)
//            _reverse(jl, jr, l, mid, i << 1);
//        if (jr >= mid + 1)
//            _reverse(jl, jr, mid + 1, r, i << 1 | 1);
//        up(i,l,r);
//    }
//}void update(int jl, int jr, int jv, int l, int r, int i)   
//{
//    if (l >= jl && r <= jr)
//    {
//       
//        ulazy(i, r - l + 1,jv);
//    }
//    else
//    {
//        int mid = (l + r) >> 1;
//        down(i, mid - l + 1, r - mid);
//        if (jl <= mid)
//            update(jl, jr, jv, l, mid, i << 1);
//        if (jr >= mid + 1)
//            update(jl, jr, jv, mid + 1, r, i << 1 | 1);
//        up(i,l,r);
//    }
//}
//const int NN = 2049;
//int tree1[NN][NN];
//int tree2[NN][NN];
//int tree3[NN][NN];
//int tree4[NN][NN];
//int n, m;
////int lowbit(int i)
////{
////    return(i & -i);
////}
//void add1(int x, int y, int v)
//{
//    int v1 = v;
//    int v2 = v * x;
//    int v3 = v * y;
//    int v4 = x * y * v;
//    for (int i = x; i <= n; i += (lowbit(i)))
//    {
//        for (int j = y; j <= m; j += lowbit(j))
//        {
//            tree1[i][j] += v1;
//            tree2[i][j] += v2;
//            tree3[i][j] += v3;
//            tree4[i][j] += v4;
//        }
//    }
//}
//void add1(int a, int b, int c, int d,int v)
//{
//    add1(a, b, v);
//    add1(c+1, b, -v);
//    add1(a, d+1, -v);
//    add1(c+1, d+1, v);
//}
//int query1(int x, int y)
//{
//    int ans = 0;
//    for (int i = x; i > 0; i -= lowbit(i))
//    {
//        for (int j = y; j > 0; j -= lowbit(j))
//        {
//            ans += ((x+1)*(y+1)*tree1[i][j]);
//            ans -= ((y+1)*tree2[i][j]);
//            ans -= ((x+1)*tree3[i][j]);
//            ans += tree4[i][j];
//        }
//    }
//    return ans;
//}
//int query(int a, int b, int c, int d)
//{
//    return query1(a-1, b-1) + query1(c, d) - query1(a - 1, d) - query1(c, b - 1);
//}
/*   int tree1[114514];
   int tree2[114514];
   int n;
   void add1(int* tree,int i, int v)
   {
       while (i <= n)
       {
           tree[i] += v;
           i += (i & -i);
       }
   }
   void add12(int l, int r, int v)
   {
       add1(tree1,l, v);
       add1(tree1,r+1, -v);
       add1(tree2,l, (l - 1) * v);
       add1(tree2,r+1, -(r * v));
   }
   int query1(int * tree,int i)
   {
       int ans = 0;
       while (i)
       {
           ans += tree[i];
           i -= (i & -i);
       }
       return ans;
   }
   int query(int l,int r)
   {
       return r * query1(tree1, r) - query1(tree2, r) - (l - 1) * query1(tree1, l - 1) + query1(tree2, l - 1);
   }*/
   /* auto adj = [&]() {//set维护中位数板子
       if (ma.size() >= mi.size() + 3)
       {
           auto a = ma.begin();
           suma += *a;
           sumb -= *a;
           mi.insert(*a);
           ma.erase(a);
       }
       if (ma.size() > mi.size())return;
       auto a = --mi.end();
       suma -= *a;
       sumb += *a;
       ma.insert(*a);
       mi.erase(a);
   };*/
   //    int wwr[1001];
   //int find(int x)
   //{
   //    if (x != wwr[x])
   //    {
   //        int w = find(wwr[x]);
   //        wwr[x] = w;
   //        return w;
   //    }
   //    else
   //    {
   //        return x;
   //    }
   //}
   //void wbwb(int a, int b)
   //{
   //    int fa = find(a);
   //    int fb = find(b);
   //    if (fa != fb)
   //    {
   //        wwr[fa] = fb;
   //       // cnt[fb] += cnt[fa];
   //    }
   //}
       //int prime[1000010] = { 0 };//质数
       //int minp[1000010] = { 0 };//最小质因子
       //void olshai(int n)
       //{
       //    int cnt = 0;
       //    for (int i = 2; i <= n; i++)
       //    {
       //        if (minp[i] == 0) { minp[i] = i; prime[++cnt] = i; }
       //        for (int j = 1; j <= cnt; j++) { if (prime[j] > minp[i] || prime[j] > n / i) break; minp[i * prime[j]] = prime[j]; }
       //    }
       //
       //}
     /*  auto dij = [&](int s, int d[], bool vis[]) {
           priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
           for (int i = 0; i <= 1 * n; i++)
               d[i] = 1e18, vis[i] = 0;
           d[s] = 0;
           q.push({ 0,s });
           while (q.size()) {
               auto t = q.top();
               q.pop();
               int u = t.second;
               if (vis[u]) continue;
               vis[u] = true;
               for (auto ed : arr[u]) {
                   int v = ed.first, w = ed.second;
                   if (d[v] > d[u] + w) {
                       d[v] = d[u] + w;
                       q.push({ d[v],v });
                   }
               }
           }
       };*/
   /*    int mergesort(vector<int>& nums, int l, int r)
       {
           long long ret = 0;
           if (l >= r)
               return 0;
           int mid = (l + r) >> 1;
           ret = (ret + mergesort(nums, l, mid)) % mod;
           ret = (ret + mergesort(nums, mid + 1, r)) % mod;
           int cur1 = l, cur2 = mid + 1, i = l;
           while (cur1 <= mid && cur2 <= r)
           {
               if (nums[cur1] <= nums[cur2])
               {
                   tem[i++] = nums[cur1++];
               }
               else {
       
                   ret = ((ret + mid) % mod - cur1 + 1) % mod;
                   tem[i++] = nums[cur2++];
       
               }
           }
           while (cur1 <= mid)tem[i++] = nums[cur1++];
           while (cur2 <= r)tem[i++] = nums[cur2++];
           for (int i = l; i <= r; i++)
               nums[i] = tem[i];
           return ret % mod;
       }*/
       //int InversePairs(vector<int>& nums) {
       //    tem.resize(nums.size());
       //    return mergesort(nums, 0, nums.size() - 1) % mod;
       //}
       //多重背包模板
       // int n, m;
       //int a[101];
       //int b[101];
       //int c[101];
       //int dp[40000 + 1];
       //int que[50000 + 100000 + 1]; cin >> n >> m;
       //for1
       //{
       //    cin >> a[i] >> b[i] >> c[i];
       //}
       //
       //for1
       //{
       //
       //
       //for (int md = 0; md <= min(m , b[i] - 1); md++)
       //{
       //    int l = 0, r = 0;
       //
       //    for (int j = m - md,k = 0; j >= 0 && k <= c[i]; j -= b[i],k++)
       //    {
       //        while (l < r && dp[que[r - 1]] <= dp[j] + a[i] * ((que[r - 1] - j) / b[i]))
       //        {
       //            r--;
       //        }
       //        que[r++] = j;
       //
       //    }
       //    for (int j = m - md; j >= 0; j -= b[i])
       //    {
       //
       //        dp[j] = dp[que[l]] + a[i] * ((j - que[l]) / b[i]);  
       //        if (j == que[l])l++;
       //        int wwr = j - b[i] * (c[i] + 1);
       //        if (wwr >= 0)
       //        { 
       //            while (l < r && dp[que[r - 1]] <= dp[wwr] + a[i] * ((que[r - 1] - wwr) / b[i]))
       //                r--;
       //            que[r++] = wwr;
       //        }
       //    }
       //}
       //
       //}
       //cout << dp[m] << endl;..
       //  vector :c.assign(beg, end)	将另外一个容器[x.begin(), x.end()) 里的内容拷贝到c中
       //vector<int>::iterator it;
       // 相当于声明了一个迭代器类型的变量it
       //less<int> 表示数字大的优先级大，堆顶为最大的数字
       //greater<int>表示数字小的优先级大，堆顶为最小的数字，优先队列比较要写结构体cmp
       //mp.lower_bound()	返回一个迭代器，指向键值 >= key的第一个元素
       //mp.upper_bound()	返回一个迭代器，指向键值 > key的第一个元素             for(auto [x, y] : mp)
       //getline(cin, s)会获取前一个输入的换行符，需要在前面添加读取换行符的语句。如：getchar() 或 cin.get()
       //tolower(s[i])	转换为小写
       //toupper(s[i])	转换为大写
       //transform(s.begin(), s.end(), s.begin(), ::tolower);//转换小写
       //transform(s.begin(), s.end(), s.begin(), ::toupper);//转换大写 find返回-1是找不到
       //bitset<n> a(s)	a是string对象s中含有的位串的副本
       //bitset<n> a(s, pos, n)	a是s中从位置pos开始的n个位的副本 bitset可以进行位操作可以通过 [] 访问元素 
       //b.count()	b中为1的个数
       //fill(a.begin(), a.end(), x)填充
       //tuple获取对应元素的值通过get<n>(tuple)方法获取, n必须为数字不能是变量
       //tie可以让tuple变量中的三个值依次赋到tie中的三个变量中tie(one, two, three) = t;
       //accumulate(beg, end, init)作用：对一个序列的元素求和init为对序列元素求和的初始值返回值类型：与init 相同
       //atoi(const char*)将字符串转换为int类型int a = atoi(s.c_str());
       //is_sorted(beg, end) 判断序列是否有序（升序），返回bool值
       //iota(beg, end，初始值)让序列递增赋值如 把数组赋值为：0 1 2 3 4 5
       //max_element+min_element找最大最小值
       ////找到a,b,c,d的最大值和最小值
       //mx = max({ a, b, c, d });
       //mn = min({ a, b, c, d });
       //nth_element(beg, nth, end)复杂度： 平均O(N)O(N)寻找第序列第n小的值
       //shuffle(b.begin(), b.end()); 随机打乱序列的顺序
       //reverse(beg, end)对序列进行翻转
       //stable_sort区别在于stable_sort()能够保证相等元素的相对位置，排序时不会改变相等元素的相对位置
       //unique(beg, end)消除重复元素，返回消除完重复元素的下一个位置的地址
       // 消除重复元素一般需要原序列是有序序列 unique 之后 a 数组为 { 1, 2, 3, 6, 3 }前面为无重复元素的数组，后面则是重复元素移到后面，返回a[4]
       //int len = unique(b, b + n) - b;//消除 b 的重复元素，并获取长度
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 11964kb

input:

3 5
1 2 3
3 4
2 -2
1 -3
3 1
2 1

output:

1
2
2
2
3

result:

ok 5 number(s): "1 2 2 2 3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 11892kb

input:

3 5
1 2 3
3 4
2 -2
1 3
3 1
2 1

output:

1
2
1
2
1

result:

ok 5 number(s): "1 2 1 2 1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 9880kb

input:

1 1
1000000000
1 1000000000

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5784kb

input:

1 1
-1000000000
1 -1000000000

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 1ms
memory: 12036kb

input:

1000 1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

946
65
252
410
915
592
983
487
343
899
809
432
586
587
139
464
804
84
476
699
504
149
579
352
375
856
545
166
140
657
568
509
275
710
873
430
537
879
301
1
298
970
923
510
984
642
55
879
941
344
464
788
917
994
571
610
491
442
926
101
986
840
624
613
425
345
816
423
275
221
317
113
386
116
469
260
4...

result:

ok 1000 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 11888kb

input:

1000 1000
1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000...

output:

500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
...

result:

ok 1000 numbers

Test #7:

score: 0
Accepted
time: 0ms
memory: 10064kb

input:

1000 1000
-485078954 -474724347 -284958745 -99994191 -853392841 -796786314 -87134718 -861459498 -982809180 -184620712 -618476092 -244916830 -349486182 -751407510 -874417202 -419521829 -888338757 -735353446 -426330733 -715383449 -48093437 -359419189 -474876639 -887614191 -157085227 -51186523 -4851821...

output:

2
3
4
5
6
7
8
9
10
11
12
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
51
52
53
54
55
56
57
58
59
60
60
61
62
63
64
65
65
66
67
68
69
70
71
72
73
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
88
89
90
91
92
92
93
94
95
96...

result:

ok 1000 numbers

Test #8:

score: 0
Accepted
time: 2ms
memory: 12100kb

input:

1000 1000
692178227 662595541 345515063 991152011 835514013 25683568 123726285 66892783 865428606 354216625 814472013 533064716 948349754 361975669 37940082 869044119 662812642 803704097 146471883 707522800 739525519 193714172 427089913 397196213 189039234 246429967 813126715 687459477 71112534 8404...

output:

43
51
56
64
65
74
75
86
87
95
101
108
113
120
128
133
138
139
139
144
145
148
151
156
156
158
160
161
166
168
172
174
178
181
184
187
187
189
191
194
198
202
205
206
207
209
208
208
212
213
213
212
215
219
220
221
222
223
225
228
231
234
235
235
236
236
238
238
241
243
244
244
247
247
247
248
249
25...

result:

ok 1000 numbers

Test #9:

score: 0
Accepted
time: 2ms
memory: 10040kb

input:

1000 1000
574468116 94882719 344585092 303636576 860857354 553186159 965991069 700277773 418699098 303119379 321049044 311046263 246185690 843955069 991766564 157610065 845367822 6325150 14241791 204057976 158548256 378251315 960460247 976973909 903759916 617675386 774999095 700647307 182260243 3951...

output:

1
1
1
44
62
62
62
62
62
62
62
63
75
86
86
94
94
94
94
94
94
101
106
110
109
109
110
110
114
118
120
120
125
133
137
142
149
151
151
154
158
163
164
164
166
171
166
171
171
176
178
178
178
182
184
189
191
192
192
193
194
194
199
199
200
200
200
201
201
202
202
203
203
203
203
204
205
209
211
213
216
...

result:

ok 1000 numbers

Test #10:

score: 0
Accepted
time: 0ms
memory: 12072kb

input:

1000 1000
751725297 937235315 680091610 26186557 254796915 744252261 881884780 923597346 266936883 546989425 417560660 89027810 544021626 957338248 904123848 814772232 101551928 545382694 250607919 995560445 577570993 931384678 862426799 261784312 954917086 283888096 73307963 303769720 219779023 411...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 1000 numbers

Test #11:

score: 0
Accepted
time: 0ms
memory: 9948kb

input:

1000 1000
-508752650 194148329 -801456523 151112987 832369235 -688290588 806491091 836936846 -122281173 356992850 -568184583 -516872363 165777265 -971767664 709095458 287512288 -240509024 222892519 809890680 -240691276 -160995890 -941338137 -110422024 -171235654 137147409 269779505 791942508 8316469...

output:

502
501
501
501
501
500
500
501
501
501
501
501
501
501
500
500
501
501
501
500
501
500
499
499
498
497
497
496
496
496
496
496
496
495
496
495
495
495
495
495
495
496
496
496
496
497
497
496
495
495
495
495
495
495
494
495
495
495
496
496
496
495
495
494
493
494
494
494
493
494
495
495
494
494
493
...

result:

ok 1000 numbers

Test #12:

score: 0
Accepted
time: 2ms
memory: 11968kb

input:

1000 1000
668917653 -912360220 -484296636 877719068 -532863859 -652299905 349419681 -27295020 117337504 915047258 669717799 -747101717 26685070 -475274955 944477505 -234513487 454335340 -77938580 827974643 579724786 32112764 -906575069 136172094 -160983053 -178633432 191196169 -702355948 -224063041 ...

output:

490
491
491
491
491
491
491
492
491
491
491
491
490
491
491
492
491
492
492
491
491
491
492
493
492
493
492
492
491
491
490
491
491
492
492
491
491
491
492
492
493
493
494
495
495
494
495
494
493
494
494
494
495
494
493
492
493
493
493
492
491
491
491
490
490
491
491
490
491
491
490
489
489
490
490
...

result:

ok 1000 numbers

Test #13:

score: 0
Accepted
time: 52ms
memory: 13964kb

input:

200000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

72376
101111
115499
58115
162542
118228
127603
92640
159784
158521
23443
120553
3776
74867
53743
144513
110937
175487
110103
155120
90227
14151
141505
165956
73915
122548
124144
170214
87824
60252
31007
63702
179573
141360
166667
31159
15231
115256
166707
175939
169172
147787
1411
98677
10409
185322...

result:

ok 200000 numbers

Test #14:

score: 0
Accepted
time: 35ms
memory: 13812kb

input:

200000 200000
1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -1000000000 1 -100...

output:

100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000
100000...

result:

ok 200000 numbers

Test #15:

score: 0
Accepted
time: 221ms
memory: 32552kb

input:

200000 200000
-641536243 -965183184 -141619591 -549578174 -605343285 -234948471 -911248231 -720193527 -374462595 -876901055 -305631438 -321131226 -273535990 -24800331 -302573198 -104933640 -943270107 -991477211 -671845994 -877636895 -967575238 -964139845 -414345700 -424981584 -72662072 -55397356 -69...

output:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102...

result:

ok 200000 numbers

Test #16:

score: -100
Wrong Answer
time: 230ms
memory: 30544kb

input:

200000 200000
535720938 467103996 857450438 172971807 714967349 587521411 299612773 913191463 178807897 661936283 790880177 161883029 24299945 457179067 314816794 183632306 607881293 211143843 900956623 913865574 820043720 588993518 487620852 859828820 273462389 315848062 600304728 176203396 8209093...

output:

546
590
723
815
911
1092
1234
1331
1383
1431
1546
1570
1606
1688
1775
1865
1924
1928
2018
2102
2146
2222
2283
2310
2367
2434
2509
2527
2528
2605
2643
2681
2694
2725
2773
2798
2815
2878
2915
2970
2982
3042
3095
3135
3152
3208
3232
3281
3331
3387
3433
3484
3539
3542
3585
3629
3634
3653
3664
3703
3732
...

result:

wrong answer 139299th numbers differ - expected: '99850', found: '99849'
English 繁體中文 简体中文

Server Time: 2024-12-04 05:04:03 | OpenSource Project