# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
202982 | MKopchev | 새로운 문제 (POI11_met) | C++14 | 1521 ms | 39720 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int nmax=3e5+42;
int states;
int n,inp[nmax];
vector<int> seen[nmax];
int want[nmax];
int samples;
struct sample
{
int l,r,add;
};
sample all[nmax];
int output[nmax];
long long fenwick[nmax];
void update(int pos,int add)
{
while(pos<=n)
{
fenwick[pos]+=add;
pos=pos+(pos&(-pos));
}
}
void on(int l,int r,int add)
{
update(l,add);
update(r+1,-add);
}
void note(int id,int mult)
{
int add=mult*all[id].add;
if(all[id].l<=all[id].r)on(all[id].l,all[id].r,add);
else {on(1,all[id].r,add);on(all[id].l,n,add);}
}
long long query(int pos)
{
long long ret=0;
while(pos)
{
ret=ret+fenwick[pos];
pos=pos-(pos&(-pos));
}
return ret;
}
bool proper(int id)
{
long long now=0;
for(auto k:seen[id])
{
now=now+query(k);
if(now>=want[id])return 1;
}
return 0;
}
void solve(vector<int> active,int l,int r)
{
if(l>r)return;
//everything in [1, l-1] is added
/*
cout<<l<<" "<<r<<" "<<(l+r)/2<<endl;
cout<<"query: ";
for(int i=1;i<=n;i++)
cout<<query(i)<<" ";cout<<endl;
*/
int av=(l+r)/2;
for(int i=l;i<=av;i++)
note(i,1);
vector<int> satisfied={},unsatisfied={};
for(auto k:active)
{
if(proper(k)){satisfied.push_back(k);output[k]=av;}
else unsatisfied.push_back(k);
}
solve(unsatisfied,av+1,r);
for(int i=l;i<=av;i++)
note(i,-1);
solve(satisfied,l,av-1);
}
int main()
{
scanf("%i%i",&states,&n);
for(int i=1;i<=n;i++)
{
scanf("%i",&inp[i]);
seen[inp[i]].push_back(i);
}
for(int i=1;i<=states;i++)scanf("%i",&want[i]);
scanf("%i",&samples);
for(int i=1;i<=samples;i++)
scanf("%i%i%i",&all[i].l,&all[i].r,&all[i].add);
for(int i=1;i<=states;i++)output[i]=samples+1;
vector<int> active={};
for(int i=1;i<=states;i++)active.push_back(i);
solve(active,1,samples);
for(int i=1;i<=states;i++)
if(output[i]>samples)printf("NIE\n");
else printf("%i\n",output[i]);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |