Submission #1255547

#TimeUsernameProblemLanguageResultExecution timeMemory
1255547free_de_la_zenithMeteors (POI11_met)C++20
0 / 100
132 ms131072 KiB
/** * 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 up upper_bound #define count_bit1(x) __builtin_popcountll(x) #define count_bit01(x) __builtin_clzll(x) #define count_bit10(x) __builtin_ctzll(x) using namespace std; #define int long long const int N=3e5+5; int L[N],R[N],lo[N],hi[N],a[N],b[N],n,m,p[N],mid[N]; vector<int>pos[N]; long long t[N]; void update(int x,ll 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,long long x) { if(l>r) return; update(l,x); update(r+1,-x); } signed 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<=q;i++) { lo[i]=1; hi[i]=q+1; } while(true) { bool ok=0; vector<vector<int>>g(n+1,vector<int>(n+1,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; memset(t,0,sizeof t); 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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...