Submission #1296282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296282		arianshabaani	Meteors (POI11_met)	C++20	100 / 100	4893 ms	27852 KiB

met

// #inclue <iostream>
#include <bits/stdc++.h>
using namespace std;
//ifstream fin("input.txt");
//ofstream fout("output.txt");

// #CONFIG
string outone = "YES";
string outtwo = "NO";

const int inf=1e9;
const int mod=1e9+7;
const int modd = 998244353;
const int maxn25=2*1e5+10;
const int maxn55=5*1e5+10;
const int maxn5=1e5+10;
const int maxn7=1e7+10;
const int maxn9=1e9+10;

#define ll long long int
#define ull unsigned long long int
#define pass cerr << "Pass shod!" << endl
#define testc ll tt; cin >> tt; while(tt--)
#define pb push_back
#define mp(i, j) make_pair(i, j)
#define moew cin.tie(0); cout.tie(0); ios::sync_with_stdio(false)
#define one first
#define two second
#define enld endl
#define neld endl
#define ednl endl
#define vectoR vector
#define cosnt const
#define ppq priority_queue
#define t1 __builtin_popcount
#define rip return 0
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef priority_queue<pll, vector<pll>, greater<pll>> pq;
typedef int itn;

void yes() { cout << "YES" << endl; }
void no() { cout << "NO" << endl; }
void out1() { cout << outone << endl; }
void out2() { cout << outtwo << endl; }
ll max3 (ll a, ll b, ll c) { return max(a, max(b, c)); }
ll min3 (ll a, ll b, ll c) { return min(a, min(b, c)); }
ll ceill (ll a, ll b) { return (a+b-1)/b; }
long double flor(long double a){ return floor(a+0.5); }
ll logg (ll a, ll b) { return log(a)/log(b); }

cosnt int maxn = 3e5+10;
int ans[maxn];
ll p[maxn];
bool mark[maxn];
ll j[maxn];
ll jj[maxn];
ll jq[maxn];
ll ps[maxn];
ll ne[maxn];
vector<int> a[maxn];
const int sq = 550;
vector<int> po;
vector<pair<pii, pii>> lq;

int main(){
    moew;
    int n, m;
    cin >> n >> m;
    for (int i=1; i<=m; i++){
        cin >> p[i];
        a[p[i]].pb(i);
    }
    for (int i=1; i<=n; i++){
        cin >> ne[i];
    }
    int q;
    cin >> q;
    for (int qq=1; qq<=q; qq++){
        ll b, c, d;
        cin >> b >> c >> d;
        if (b>c){
            ps[b]+=d;
            ps[1]+=d;
            ps[c+1]-=d;
        }else {
            ps[b]+=d;
            ps[c+1]-=d;
        }
        lq.pb({{b, c}, {d, qq}});
        if (qq%sq==0){
            po.clear();
            for (int i=1; i<=m; i++){
                ps[i]+=ps[i-1];
                jj[p[i]]+=ps[i];
                if (j[p[i]]+jj[p[i]]>=ne[p[i]] and !mark[p[i]]){
                    po.pb(p[i]);
                    mark[p[i]]=1;
                }
            }
            for (auto v : po){
                for (auto [k, ki] : lq){
                    auto [b, c] = k;
                    auto [d, in]=ki;
                    ll an = 0;
                    for (auto u : a[v]){
                        if (b>c){
                            if ((u>=1 and u<=c) or (u>=b and u<=m)){
                                an++;
                            }
                        }else {
                            if (u>=b and u<=c){
                                an++;
                            }
                        }
                    }
                    bool f = 0;
                    if (jq[v]+j[v]<ne[v]){
                        f=1;
                    }
                    jq[v]+=an*d;
                    if (jq[v]+j[v]>=ne[v] and f){
                        ans[v]=in;
                    }
                }
            }
            for (int i=1; i<=m; i++){
                ps[i]=0;
                j[p[i]]+=jj[p[i]];
                jj[p[i]]=0;
                jq[p[i]]=0;
            }
            lq.clear();
        }
    }
    po.clear();
    for (int i=1; i<=m; i++){
        ps[i]+=ps[i-1];
        jj[p[i]]+=ps[i];
        if (j[p[i]]+jj[p[i]]>=ne[p[i]] and !mark[p[i]]){
            po.pb(p[i]);
            mark[p[i]]=1;
        }
    }
    for (auto v : po){
        for (auto [k, ki] : lq){
            auto [b, c] = k;
            auto [d, in]=ki;
            ll an = 0;
            for (auto u : a[v]){
                if (b>c){
                    if ((u>=1 and u<=c) or (u>=b and u<=m)){
                        an++;
                    }
                }else {
                    if (u>=b and u<=c){
                        an++;
                    }
                }
            }
            bool f = 0;
            if (jq[v]+j[v]<ne[v]){
                f=1;
            }
            jq[v]+=an*d;
            if (jq[v]+j[v]>=ne[v] and f){
                ans[v]=in;
            }
        }
    }
    for (int i=1; i<=n; i++){
        if (ans[i]==0){
            cout << "NIE" << endl;
        }else {
            cout << ans[i] << endl;
        }
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13