oj.uz

Submission #967425

# Submission time Handle Problem Language Result Execution time Memory
967425 2024-04-22T05:28:10 Z 12345678 Meteors (POI11_met) C++17
100 / 100
 1676 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=4e5+5;

int n, m, p[nx], q, l[nx], r[nx], ul, ur, a, cnt=19, t[nx];
vector<int> d[nx], qrs[nx];
vector<pair<int, pair<int, int>>> k;

struct fenwick
{
    ll d[nx];
    void update(int i, int vl) 
    {
        while (i<nx) d[i]+=vl, i+=(i&-i);
    }
    ll query(int i)
    {
        ll res=0;
        while (i>0) res+=d[i], i-=(i&-i);
        return res;
    }
} f;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>p[i], d[p[i]].push_back(i);
    for (int i=1; i<=n; i++) cin>>t[i];
    cin>>q;
    for (int i=0; i<q; i++) cin>>ul>>ur>>a, k.push_back({a, {ul, ur}});
    for (int i=1; i<=n; i++) l[i]=1, r[i]=q+1;
    while (cnt--)
    {
        for (int i=1; i<=n; i++) if (l[i]!=r[i]) qrs[(l[i]+r[i])/2].push_back(i);
        for (int i=1; i<=q+1; i++)
        {
            if (i==q+1) continue;
            int x=k[i-1].second.first, y=k[i-1].second.second, z=k[i-1].first;
            if (x<=y) f.update(x, z), f.update(y+1, -z);
            else f.update(1, z), f.update(y+1, -z), f.update(x, z), f.update(m+1, -z);
            //cout<<"fenwick "<<i<<':';
            //for (int j=1; j<=m; j++) cout<<f.query(j)<<' ';
            //cout<<'\n';
            for (auto idx:qrs[i])
            {
                ll sm=0;
                for (auto id:d[idx]) sm+=f.query(id), sm=min(sm, (ll)t[idx]+1);
                //cout<<"debug "<<cnt<<' '<<idx<<' '<<sm<<'\n';
                if (sm>=t[idx]) r[idx]=i;
                else l[idx]=i+1;
            }
            qrs[i].clear();
        }
        for (int i=1; i<=m+1; i++) f.d[i]=0;
    }
    for (int i=1; i<=n; i++)
    {
        if (l[i]>q) cout<<"NIE\n";
        else cout<<l[i]<<'\n';
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19292 KB Output is correct
2 Correct 10 ms 19292 KB Output is correct
3 Correct 10 ms 19292 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19292 KB Output is correct
2 Correct 10 ms 19292 KB Output is correct
3 Correct 11 ms 19292 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 21196 KB Output is correct
2 Correct 143 ms 23084 KB Output is correct
3 Correct 95 ms 23136 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 22216 KB Output is correct
2 Correct 111 ms 22176 KB Output is correct
3 Correct 149 ms 23296 KB Output is correct
4 Correct 29 ms 21572 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 21704 KB Output is correct
2 Correct 120 ms 23752 KB Output is correct
3 Correct 134 ms 19996 KB Output is correct
4 Correct 97 ms 23240 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 20740 KB Output is correct
2 Correct 137 ms 22168 KB Output is correct
3 Correct 78 ms 20936 KB Output is correct
4 Correct 122 ms 24564 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 39984 KB Output is correct
2 Correct 822 ms 28024 KB Output is correct
3 Correct 651 ms 24752 KB Output is correct
4 Correct 1377 ms 65536 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 876 ms 38704 KB Output is correct
2 Correct 662 ms 27984 KB Output is correct
3 Correct 527 ms 25144 KB Output is correct
4 Correct 1676 ms 65536 KB Output is correct