QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#342791#2557. Lagbachbeo2007WA 3ms36672kbC++237.1kb2024-03-01 16:54:162024-03-01 16:54:16

Judging History

你现在查看的是最新测评结果

  • [2024-03-01 16:54:16]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:36672kb
  • [2024-03-01 16:54:16]
  • 提交

answer

// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=250005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=20;
const int Max=250001;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=101;

int dx[]={1,1,0,-1,-1,-1,0,1},
    dy[]={0,1,1,1,0,-1,-1,-1};

int n,m,q;
int res[maxn];
int X[maxn],Y[maxn];

bool mv[maxn];
struct Rec{
    int x1,y1,x2,y2;
    Rec(){}
}rec[maxn];

struct Query{
    int x1,y1,x2,y2,val;
};

namespace Left_to_Right{
    int tree[4*maxn],lazy[4*maxn];
    void getnew(int l,int r,int id,int val){
        lazy[id]+=val;
        tree[id]+=(r-l+1)*val;
    }
    void pushdown(int l,int r,int id){
        if(!lazy[id]) return;
        int mid=(l+r)>>1;
        getnew(l,r,id<<1,lazy[id]);
        getnew(mid+1,r,id<<1|1,lazy[id]);
        lazy[id]=0;
    }
    void update(int l,int r,int id,int tl,int tr,int val){
        if(tr<l || r<tl) return;
        if(tl<=l && r<=tr){
            getnew(l,r,id,val);
            return;
        }
        pushdown(l,r,id);
        int mid=(l+r)>>1;
        update(l,mid,id<<1,tl,tr,val);update(mid+1,r,id<<1|1,tl,tr,val);
        tree[id]=tree[id<<1]+tree[id<<1|1];
    }
    int query(int l,int r,int id,int p){
        if(l==r) return tree[id];
        pushdown(l,r,id);
        int mid=(l+r)>>1;
        if(p<=mid) return query(l,mid,id<<1,p);
        else return tree[id<<1]+query(mid+1,r,id<<1|1,p);
    }

    vector<piii> pos[maxn];
    void solve(vector<Query> Q,vector<piii> qq){
        for(int i=0;i<=Max;i++) pos[i].clear();
        for(int i=0;i<=4*Max;i++) tree[i]=lazy[i]=0;

        for(auto c:Q) pos[c.x1].push_back({c.val,{c.y1,c.y2}});
        for(auto p:qq) pos[p.se.fi].push_back({0,{p.fi,p.se.se}});
        for(int i=0;i<=Max;i++){
            for(auto p:pos[i]){
                if(p.fi) update(0,Max,1,p.se.fi,p.se.se,p.fi);
                else res[p.se.fi]+=query(0,Max,1,p.se.se);
            }
        }
    }
}

namespace Down_to_Up{
    vector<pii> pos[maxn];

    struct bit{
        int bit[2*maxn];
        void update(int x,int val){
            assert(x>0);
            for(int i=x;i<=2*Max;i+=(i&(-i))) bit[i]+=val;
        }
        int query(int x){
            assert(x>=0);
            int total=0;
            for(int i=x;i>=1;i-=(i&(-i))) total+=bit[i];
            return total;
        }
    }f0,f1,f2;

    void cal(vector<Query> Q,vector<piii> qq){
        for(int i=0;i<=2*Max;i++) f0.bit[i]=f1.bit[i]=f2.bit[i]=0;
        for(int i=0;i<=Max;i++) pos[i].clear();
        for(int i=0;i<(int)Q.size();i++){
            auto c=Q[i];
            pos[c.x1].emplace_back(inf,i);
            pos[c.x2+1].emplace_back(-inf,i);
        }
        for(auto p:qq) if(p.se.fi>=0) pos[p.se.fi].emplace_back(p.fi,p.se.se);
        for(int i=0;i<=Max;i++){
            for(auto p:pos[i]){
                if(p.fi==-inf){
                    int d=Q[p.se].x1-Q[p.se].y1,val=Q[p.se].val;
                    f0.update(Max-d,-val);
                    f1.update(Max-d,val*(Q[p.se].x1-1));
                    f2.update(Max-d,val*(Q[p.se].x2-Q[p.se].x1+1));
                }
                else if(p.fi==inf){
                    int d=Q[p.se].x1-Q[p.se].y1,val=Q[p.se].val;
                    f0.update(Max-d,val);
                    f1.update(Max-d,-val*(i-1));
                }
                else{
                    res[p.fi]+=f0.query(Max-(i-p.se))*i+f1.query(Max-(i-p.se))+f2.query(Max-(i-p.se));
                }
            }
        }
    }
    void solve(vector<Query> Q,vector<piii> qq){
        cal(Q,qq);
        for(auto &c:Q){
            swap(c.x1,c.y1);
            swap(c.x2,c.y2);
        }
        for(auto &p:qq){
            p.se.fi--;
            swap(p.se.fi,p.se.se);
        }
        cal(Q,qq);
    }
}

void solve(){
    cin >> n >> m >> q;
    for(int i=1;i<=n;i++) cin >> rec[i].x1 >> rec[i].y1 >> rec[i].x2 >> rec[i].y2;

    vector<Query> q0,q1,q2,q3;

    auto add = [&](int x1,int y1,int x2,int y2,int val){
        if(x1>x2 || (x1==x2 && y1>y2)){
            swap(x1,x2);
            swap(y1,y2);
        }
        if(y1==y2) q1.push_back({y1,x1,y2,x2,val});
        else if(x1==x2) q0.push_back({x1,y1,x2,y2,val});
        else if(x1-y1==x2-y2) q2.push_back({x1,y1,x2,y2,val});
        else q3.push_back({Max-x2+1,y2,Max-x1+1,y1,-val});
    };

    for(int i=1;i<=m;i++){
        int id,p,d;cin >> id >> p >> d;

        Rec S=rec[p];
        S.x1+=dx[id]*mv[p];
        S.y1+=dy[id]*mv[p];
        S.x2+=dx[id]*mv[p];
        S.y2+=dy[id]*mv[p];
        mv[p]=true;
        rec[p].x1+=dx[id]*d;
        rec[p].y1+=dy[id]*d;
        rec[p].x2+=dx[id]*d;
        rec[p].y2+=dy[id]*d;
        Rec T=rec[p];

        add(S.x1,S.y1,T.x1,T.y1,1);
        add(S.x2+1,S.y1,T.x2+1,T.y1,-1);
        add(S.x1,S.y2+1,T.x1,T.y2+1,-1);
        add(S.x2+1,S.y2+1,T.x2+1,T.y2+1,1);
    }
    for(int i=1;i<=n;i++){
        if(mv[i]) continue;
        Rec S=rec[i],T=S;
        add(S.x1,S.y1,T.x1,T.y1,1);
        add(S.x2+1,S.y1,T.x2+1,T.y1,-1);
        add(S.x1,S.y2+1,T.x1,T.y2+1,-1);
        add(S.x2+1,S.y2+1,T.x2+1,T.y2+1,1);
    }

    vector<piii> qq;
    for(int i=0;i<q;i++){
        cin >> X[i] >> Y[i];
        qq.push_back({i,{X[i],Y[i]}});
    }
    Left_to_Right::solve(q0,qq);
    Down_to_Up::solve(q2,qq);
    for(int i=0;i<q;i++){
        qq[i].se.fi=Y[i];
        qq[i].se.se=X[i];
    }
    Left_to_Right::solve(q1,qq);
    for(int i=0;i<q;i++){
        qq[i].se.fi=Max-1-X[i];
        qq[i].se.se=Y[i];
    }
    Down_to_Up::solve(q3,qq);

    for(int i=0;i<q;i++) cout << res[i] << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

详细

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 36672kb

input:

1 8 3
2 1 2 1
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
1 1
2 1
4 2

output:

0
3
1

result:

wrong answer 2nd words differ - expected: '2', found: '3'