QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#342725#2557. Lagbachbeo2007RE 9ms24936kbC++236.6kb2024-03-01 15:39:242024-03-01 15:39:24

Judging History

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

  • [2024-03-01 15:39:24]
  • 评测
  • 测评结果:RE
  • 用时:9ms
  • 内存:24936kb
  • [2024-03-01 15:39:24]
  • 提交

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 update(int l,int r,int id,int tl,int tr,int val){
        if(tr<l || r<tl) return;
        if(tl<=l && r<=tr){
            lazy[id]+=val;
            tree[id]+=(r-l+1)*val;
            return;
        }
        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];
        int mid=(l+r)>>1;
        if(p<=mid) return query(l,mid,id<<1,p)+(p-l+1)*lazy[id];
        else return tree[id<<1]+query(mid+1,r,id<<1|1,p)+(p-l+1)*lazy[id];
    }

    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){
            for(int i=x;i<=2*Max;i+=(i&(-i))) bit[i]+=val;
        }
        int query(int x){
            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<(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[i].x1-Q[i].y1,val=Q[i].val;
                    f0.update(Max-d,-val);
                    f1.update(Max-d,val*(Q[i].x1-1));
                    f2.update(Max-d,val*(Q[i].x2-Q[i].x1+1));
                }
                else if(p.fi==inf){
                    int d=Q[i].x1-Q[i].y1,val=Q[i].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(x1==x2) q0.push_back({x1,y1,x2,y2,val});
        else if(y1==y2) q1.push_back({y1,x1,y2,x2,val});
        else if(x1-y1==x2-y2) q2.push_back({x1,y2,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-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();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 24596kb

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
2
1

result:

ok 3 tokens

Test #2:

score: 0
Accepted
time: 9ms
memory: 24936kb

input:

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

output:

2
1
0

result:

ok 3 tokens

Test #3:

score: -100
Runtime Error

input:

10 10 10
45066 44774 106240 221436
22774 27403 164972 196292
35788 27798 154149 71660
8624 14258 47662 205040
9479 49585 89304 70902
24893 32999 218506 41529
27023 49837 175362 52663
21858 40287 135949 41957
12106 48095 80386 230759
41236 37600 169685 129218
7 6 5009
4 5 2577
0 5 37640
3 10 34168
1 ...

output:


result: