QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#879967 | #8074. Multiply Then Plus | Mirasycle | WA | 978ms | 245544kb | C++14 | 3.0kb | 2025-02-02 19:12:04 | 2025-02-02 19:12:05 |
Judging History
answer
#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r>>1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<pair<int,int>,int> pii;
const int maxn=5e5+10;
int n,m,qc=0; ll ans[maxn];
struct Query{
int x,l,r,id,tim;
bool operator < (const Query &rhs) const { return x<rhs.x; }
}; vector<Query> q; int val[maxn][3],t;
struct Change{
int a,b,l,r,id;
}a[maxn<<1];
int cur[maxn],tot=0;
struct SegmentTree{
struct node{
int x,y;
node operator - (const node& rhs){ return {x-rhs.x,y-rhs.y}; }
ll operator * (const node &rhs){ return 1ll*x*rhs.y-1ll*y*rhs.x; }
ll val(int k){ return 1ll*k*x+y; }
}; vector<node> s[maxn<<2]; int to[maxn<<2];
bool cmp(node s1,node s2){ return s1.x==s2.x?s1.y<s2.y:s1.x<s2.x; }
void build(int p,int l,int r){
to[p]=0;
if(l==r){ s[p].clear(); s[p].pb((node){val[l][1],val[l][2]}); return ; }
build(ls,l,mid); build(rs,mid+1,r);
s[p].resize(s[ls].size()+s[rs].size());
merge(s[ls].begin(),s[ls].end(),s[rs].begin(),s[rs].end(),s[p].begin(),
[](node s1,node s2){return s1.x!=s2.x?s1.x<s2.x:s1.y<s2.y;});
int top=-1;
for(auto z:s[p]){
while(top>=1&&(s[p][top]-s[p][top-1])*(z-s[p][top-1])>=0) top--;
s[p][++top]=z;
}
s[p].resize(top+1);
}
ll query(int p,int l,int r,int ql,int qr,int k){
if(val[r][0]<ql||val[l][0]>qr) return 0;
if(ql<=val[l][0]&&val[r][0]<=qr){
while(to[p]+1<(int)s[p].size()){
if(s[p][to[p]].val(k)<=s[p][to[p]+1].val(k)) to[p]++;
else break;
}
return s[p][to[p]].val(k);
}
ll res=0;
res=max(res,query(ls,l,mid,ql,qr,k));
res=max(res,query(rs,mid+1,r,ql,qr,k));
return res;
}
}seg;
namespace DS{
vector<pii > op[maxn<<2];
void modify(int p,int l,int r,int ql,int qr,pii z){
if(ql<=l&&r<=qr){ op[p].pb(z); return ; }
if(ql<=mid) modify(ls,l,mid,ql,qr,z);
if(qr>mid) modify(rs,mid+1,r,ql,qr,z);
}
void query(int p,int l,int r,vector<Query> vec){
if(vec.empty()) return ;
if(op[p].size()){
sort(op[p].begin(),op[p].end()); t=0;
for(auto z:op[p]) val[++t][0]=z.se,val[t][1]=z.fi.fi,val[t][2]=z.fi.se;
seg.build(1,1,t);
sort(vec.begin(),vec.end());
for(auto z:vec)
ans[z.id]=max(ans[z.id],seg.query(1,1,t,z.l,z.r,z.x));
}
if(l==r) return ; q.clear();
for(auto z:vec)
if(z.tim<=mid) q.pb(z);
query(ls,l,mid,q); q.clear();
for(auto z:vec)
if(z.tim>mid) q.pb(z);
query(rs,mid+1,r,q);
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m; tot=n;
for(int i=1;i<=n;i++){
int A,B; cin>>A>>B;
a[i]={A,B,1,m,i}; cur[i]=i;
}
for(int i=1;i<=m;i++){
int op,k,x,y;
cin>>op>>k>>x>>y;
if(op==1){
a[cur[k]].r=i-1;
cur[k]=++tot; a[tot]={x,y,i,m,k};
}else q.pb((Query){k,x,y,++qc,i});
}
for(int i=1;i<=tot;i++)
if(a[i].l<=a[i].r) DS::modify(1,1,m,a[i].l,a[i].r,mp(mp(a[i].a,a[i].b),a[i].id));
DS::query(1,1,m,q);
for(int i=1;i<=qc;i++) cout<<ans[i]<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 105828kb
input:
3 5 2 3 1 5 3 1 2 1 1 3 2 3 1 2 1 3 1 1 2 3 3 3 2 2 1 3
output:
6 9 4 7
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 11ms
memory: 106016kb
input:
1 1 2 3 2 1 1 1
output:
5
result:
ok single line: '5'
Test #3:
score: -100
Wrong Answer
time: 978ms
memory: 245544kb
input:
500000 500000 791081793 64517634 63854499 862465815 176217868 269277485 771263429 404780756 245029288 14378702 34910864 161492952 585187086 458118344 482234206 288599768 702175385 765411906 210811947 470958349 996540296 51490854 269173275 127623858 117329791 70500259 30220786 362448265 502753543 587...
output:
90673144893901202 76482591666813947 369057312490922371 27056475874815848 481680146424721383 363286612135534048 230904315882041898 0 27057837598661678 555140185012780048 613304763132407621 811896201592615375 546698494498454983 590319133230246416 183883717541797280 208602296965174881 17810662379378742...
result:
wrong answer 2nd lines differ - expected: '168977598037656727', found: '76482591666813947'