Submission #1255411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255411		free_de_la_zenith	Meteors (POI11_met)	C++20	74 / 100	562 ms	34256 KiB

met

/**
 *    author:  MINHTPC
 *
**/
#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin() , a.end()
#define FOR(i ,a , b) for(int i = a ; i <= b ; ++i)
#define bit(mask,i) ((mask>>i)&1)
#define name "task"
#define count_bit1(x) __builtin_popcountll(x)
#define count_bit01(x) __builtin_clzll(x)
#define count_bit10(x) __builtin_ctzll(x)

using namespace std;
const int N=3e5+5;
int n,m;
int p[N],a[N],t[N];
int L[N],R[N],b[N];
int lo[N],hi[N],mid[N];
void update(int x,int v) {
    for(;x<=m;x+=x&-x) t[x]+=v;
}
long long get(int x) {
    long long res=0;
    for(;x;x-=x&-x) res+=t[x];
    return res;
}
void add(int l,int r,int v) {
    if(l>r) return;
    update(l,v);
    update(r+1,-v);
}
vector<int>pos[N],g[N];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    if(fopen("umnik.inp","r")) {
        freopen("umnik.inp","r",stdin);
//        freopen("umnik.out","w",stdout);
    }
    cin >> n >> m;
    for(int i=1;i<=m;i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    for(int i=1;i<=n;i++) cin >> p[i];
    int q;
    cin >> q;
    for(int i=1;i<=q;i++) cin >> L[i] >> R[i] >> b[i];
    for(int i=1;i<=n;i++) {
        lo[i]=1;
        hi[i]=q+1;
    }
    while(true) {
        bool ok=0;
        for(int i=1;i<=q;i++) g[i].clear();
        for(int i=1;i<=n;i++) {
            if(lo[i]<hi[i]) {
                ok=1;
                mid[i]=(lo[i]+hi[i])>>1;
                g[mid[i]].push_back(i);
            }
        }
        if(!ok) break;
        fill(t,t+N,0LL);
        for(int i=1;i<=q;i++) {
            if(L[i]<=R[i]) add(L[i],R[i],b[i]);
            else {
                add(L[i],m,b[i]);
                add(1,R[i],b[i]);
            }
            for(int s:g[i]) {
                long long x=0;
                for(int v:pos[s]) {
                    x+=get(v);
                    if(x>=p[s]) break;
                }
                if(x>=p[s]) hi[s]=mid[s];
                else lo[s]=mid[s]+1;
            }
        }
    }
    for(int i=1;i<=n;i++) {
        if(lo[i]==q+1) cout << "NIE\n";
        else cout << lo[i] << '\n';
    }
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen("umnik.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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: 0 / 13
• Subtask 8: 0 / 13