QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#692478 | #9529. Farm Management | 000226# | WA | 2ms | 8624kb | C++17 | 2.1kb | 2024-10-31 14:35:02 | 2024-10-31 14:35:03 |
Judging History
answer
#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i)
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;
const int maxn=1e5+10;
int n,m;
ll sum;
int a[maxn],b[maxn];
int x[maxn],t[maxn];
vector<int>vec[maxn];
struct Ver{
int x,t;
bool operator < (const Ver &rhs)const{
if(x!=rhs.x)return x<rhs.x;
else return a[t]>=a[rhs.t];
}
};
set<Ver>S;
void Add(int p,ll pos){
while(!vec[p].empty() && vec[p].back()<=pos)vec[p].pop_back();
if(!vec[p].empty())S.insert(Ver{vec[p].back(),p});
}
set<int>rec,Pos;
vector<int>Ec[maxn];
unordered_map<int,int>Map;
int Id(int x){ if(!Map.count(x))return Map[x]=Map.size()+1; else return Map[x]; }
void solve(){
cin>>n>>m;S.clear();rec.clear();Pos.clear();Map.clear();
Rep(i,1,n)cin>>a[i],vec[i].resize(0),b[i]=a[i],rec.insert(i),Ec[i].resize(0);
Rep(i,1,m)cin>>x[i]>>t[i],vec[t[i]].emplace_back(x[i]),Pos.insert(x[i]),Ec[Id(x[i])].emplace_back(t[i]);
Rep(i,1,n){
reverse(vec[i].begin(),vec[i].end());
if(!vec[i].empty())S.insert(Ver{vec[i].back(),i});
}
ll ans=0;
while(!S.empty() || !rec.empty()){
auto ip =Pos.upper_bound(ans);
if(ip==Pos.end())break;
int nxt=*ip;
if(!S.empty()){
Ver it= *S.begin();
if(!b[it.t] || it.x<=ans)continue;
if(b[it.t]<nxt-ans){
ans+=b[it.t];b[it.t]=0;
rec.erase(it.t);
S.erase(S.begin());
}else{
b[it.t]-=(nxt-ans);
ans=nxt;
for(auto it :Ec[Map[nxt]])b[it]=a[it],Add(it,ans),rec.insert(it);
}
}else{
int it=*rec.begin();
if(b[it]<nxt-ans){
ans+=b[it];b[it]=0;
rec.erase(it);
}else{
b[it]-=(nxt-ans);
ans=nxt;
for(auto it : Ec[Map[nxt]])b[it]=a[it],Add(it,ans),rec.insert(it);
}
}
}
Rep(i,1,n)ans+=b[i];
cout<<ans<<"\n";
}
int tex;
int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>tex;while(tex--)solve(); }
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 8624kb
input:
5 17 2 3 4 6 1 5 8 2 4 4 3 3 7 5 5
output:
60 60 60 60 60
result:
wrong answer 1st lines differ - expected: '109', found: '60'