QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#929220#6692. Building Companyhuo_hua_ya#TL 17ms3840kbC++1433.5kb2025-03-08 18:24:072025-03-08 18:24:11

Judging History

This is the latest submission verdict.

  • [2025-03-08 18:24:11]
  • Judged
  • Verdict: TL
  • Time: 17ms
  • Memory: 3840kb
  • [2025-03-08 18:24:07]
  • Submitted

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 fr(i,a,b) for(int i = a;i<=b;i++)
#define cl(a)cout<<a<<endl;
#define for1 for(int i = 1;i <= n;i++)
#define for0 for(int i = 0;i < n;i++) 
#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 vi vector<int>
#define yes  cout<<"yes\n"
#define Yes  cout<<"Yes\n"
#define YES  cout<<"YES\n"
#define No cout<<"No\n"
#define no cout<<"no\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 ull unsigned long long
#define pii pair<int,int>
const int mode = 998244353;
const int mod = 1000000007;
mt19937_64 rnd(time(0));
//typedef uint64_t hash_t;
//chrono::high_resolution_clock::now().time_since_epoch().count()  
//#include <ext/pb_ds/assoc_container.hpp>
//const ull mod2 = 1000000000061;
//const ull RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
//struct chash {
//    ull operator()(ull x) const { return x ^  RANDOM ^ mod2; }
//};
//typedef __gnu_pbds::gp_hash_table<ull, ull, chash> hash_t;
// typedef unordered_map<pii, ull, chash> hash_t;
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1)ans = ans * a % mod; a = a * a % mod; b >>= 1; }return ans; }
ll qpow(ll a, ll b, ll p) { a %= p; b %= p; ll ans = 1; while (b) { if (b & 1)ans = ans * a % p; a = a * a % p; b >>= 1; }return ans; }
ll inv(ll x) { return qpow(x, mod - 2, mod); }ll inv(ll x, ll p) { return qpow(x, p - 2, p); }
int gcd(int a, int b)
{
    if (b == 0)return a;
    return gcd(b, a % b);
}
void getnext(string& b, vector<int>& nx)//整个过程就相当于对自己和自己用kmp算法,但是其中一个自己要在另一个自己前面一个元素进行匹配。
{
    int n = b.size();
    nx.resize(n + 1);
    for (int i = 1; i < n; i++) {
        int j = nx[i - 1];
        while (j > 0 && b[i] != b[j]) j = nx[j - 1];
        if (b[i] == b[j])
            j++;
        nx[i] = j;
    }
}
long long lcm(long long a, long long b)
{
    return (a * b) / gcd(a, b);
}
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;
}
void solve();
signed main()
{
    IOS;
    //T()
    {
        solve();
    }
     return 0;
}
map<int, vi>tu;
map<int, vector<pii>>sh;
map<int, vector<pii>> need;
map<int, bool>v;
void solve()
{
    int g;
    cin >> g;
    map<int, int>arr;
    for (int i = 1; i <= g; i++)
    {
        int x, y;
        cin >> x >> y;
        arr[x] += y;
    }
    int n;
    cin >> n;
    queue<int>q;
    for (int i = 1; i <= n; i++)
    {
        int m;
        cin >> m;
        while (m--)
        {
            int x, y;
            cin >> x >> y;
            tu[x].push_back(i);
            need[i].push_back({ x,y });
        }
        int k;
        cin >> k;
        while (k--)
        {
            int x, y;
            cin >> x >> y;
            sh[i].push_back({ x,y });
        }
    }
    for (int i = 1; i <= n; i++)
    {
        bool f = true;
        for (auto& z : need[i])
        {
            if (arr[z.first] < z.second)f = false;
        }
        if (f)q.push(i), v[i] = true;
    }
    int ans = 0;
    while (q.size())
    {
        ans++;
        auto z = q.front();
        q.pop();
        for (auto& wwr : sh[z])
        {
            arr[wwr.first] += wwr.second;
        }
        for (auto& wwr : sh[z])
        {
            for (auto& qq : tu[wwr.first])
            {
                if (!v[qq])
                {
                    bool f = true;
                    for (auto& nmb : need[qq])
                    {
                        if (arr[nmb.first] < nmb.second)f = false;
                    }
                    if (f)
                    {
                        q.push(qq);
                        v[qq] = true;
                    }
                }
            }
        }
    }
    cout << ans << endl;
}
//错排方案数 cnti = (i-1)*(cnti-1+cnti-2)cnt1 = 0,cnt2 =    1;
//int kmp(char* a, char* b)
//{
//    int ans = 0;
//    getnext(b);
//    int m = strlen(a);
//    int n = strlen(b);
//    int i = 0, j = 0;
//    while (i < m)
//    {
//        if (j == -1 || b[j] == a[i])//j==-1的情况是第一个字母就不匹配。如果字母匹配i和j就同时后移 
//        {
//            ++i;
//            ++j;
//        }
//        else j = nx[j];//如果匹配失败,j回溯。
//        if (j == n)//匹配成功就ans++,j回溯。
//        {
//            ans++;
//            j = nx[j];
//        }
//    }
//    return ans;
//}
/*
 while (l <= r) {
        int lmid = l + (r - l) / 3;
        int rmid = r - (r - l) / 3;
        /// 凹区间
        if (check(lmid) < check(rmid)) {
            l = lmid + 1;
        }
        else {
            r = rmid - 1;
        }
    }
    int wbwb = 0;
    cout << max({ check(l), check(r) ,0ll,check(l-1),check(r+1)}) << endl;*/
//{
//    int ret = 1;
//
//    for (auto z : a[u])
//    {
//        if (z == fa)continue;
//        int siz = dfs(z, u);
//        for (int j = 0; j <= ret + siz; j++)
//        {
//            t1[j] = 0;
//            t2[j] = 0;
//        }
//        for (int j = ret; j >= 1; j--)
//        {
//            for (int k = 0; k <= siz; k++)
//            {
//                t1[j + k] += f[u][j] * f[z][k] % mod;
//                t1[j + k] %= mod;
//                t2[j + k] += (f[u][j] * g[z][k] % mod + g[u][j] * f[z][k] % mod) % mod;
//                t2[j + k] %= mod;
//            }
//        }
//        for (int i = 1; i <= ret + siz; i++)
//        {
//            f[u][i] = t1[i];
//            g[u][i] = t2[i];
//        }
//
//        ret += siz;
//
//    }
//
//    int wwr = 0;
//    if (u != 1)for (int i = 1; i <= n; i++)
//        ans[i] = (ans[i] + (g[u][i] * ((1ll - vv[fa][1] * inv(vv[fa][2] % mod) + mod) % mod)) % mod) % mod;
//    else for (int i = 1; i <= n; i++)    ans[i] = (ans[i] + g[u][i]) % mod;
//    return ret;
//}
//void primeinit() {
    //const int N = 0;
    //int prime[N], now;
    //int minp[N];
    //bool vis[N];
    //int cnt;
    //for (int i = 2; i <= N; ++i)
    //{
    //    if (minp[i] == 0)
    //    {
    //        minp[i] = i;
    //        prime[cnt++] = i;
    //    }
    //    for (int j = 0; j < cnt; ++j)
    //    {
    //        int p = prime[j];
    //        if (i * p > N)
    //            break;
    //        //if(minp[i*p] == 0)
    //        minp[i * p] = p;
    //        if (minp[i] == p)
    //            break;
    //        //if(i%p==0) //用这个也可以
    //        //break;
    //    }
    //}
//}

//const int N = 1e6;
//int prime[N + 9 >> 1], nnow;
//bool vis[N + 9];
//void init() {
//    for (int i = 2; i <= N; i++) {
//        if (!vis[i])prime[++nnow] = i;
//        for (int j = 1; j <= nnow && prime[j] * i <= N; j++) {
//            vis[prime[j] * i] = 1;
//            if (i % prime[j] == 0)break;
//        }
//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 的重复元素,并获取长度

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2 1 1 2
5
1 3 1
0
2 1 1 2 1
2 3 2 2 1
3 1 5 2 3 3 4
1 2 5
3 2 1 1 1 3 4
1 1 3
0
1 3 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

3 610031727 590328742 816793299 18485566 654221125 47823436
10
3 610031727 224714165 816793299 491951703 654221125 593479446
1 610031727 538596643
1 610031727 551036304
3 816793299 262985484 610031727 52580932 654221125 424397787
1 654221125 889197190
3 654221125 126924193 610031727 963399336 816793...

output:

10

result:

ok 1 number(s): "10"

Test #3:

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

input:

10 720543365 814021419 777649737 273919247 339754140 472967790 545693058 298289557 949226024 176807538 267294560 819212220 337794335 504610276 137418995 614590802 632556957 783062334 587607535 115519693
100
5 949226024 327424834 777649737 117746775 137418995 152960310 720543365 423301366 267294560 4...

output:

100

result:

ok 1 number(s): "100"

Test #4:

score: 0
Accepted
time: 17ms
memory: 3712kb

input:

33 598906111 952747266 214206082 308472115 773699301 71970369 334282917 266176016 861160505 745480638 397625705 130382274 75028923 106125916 739923352 754152044 493886549 212094717 352869179 727757279 697376464 343501623 916521518 80952344 90959088 722016125 286878647 329186592 770901193 30277256 92...

output:

100

result:

ok 1 number(s): "100"

Test #5:

score: -100
Time Limit Exceeded

input:

380 562284409 583959039 705240193 694592025 91058796 151967354 775570098 571811699 457579493 117213529 684664737 33837962 60865228 186423701 316573783 868301583 744570505 934432338 790259030 364551324 145817136 961903964 737096543 759008968 865899868 681823261 273067044 247683791 186025557 756452454...

output:


result: