QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#103409	#4219. Insects	SolitaryDream^#	TL	117ms	13944kb	C++20	2.8kb	2023-05-05 18:24:54	2023-05-05 18:24:55

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-05 18:24:55]
评测

测评结果：TL
用时：117ms
内存：13944kb

查看

[2023-05-05 18:24:54]
提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+1e3+7;

int n,m;

int head[N*31],cnt=1,hd[N*31];

struct Edge{
    int ne,to,w;
}edg[N*300];

void build(int u,int v,int w)
{
    ++cnt;
    edg[cnt].to=v;
    edg[cnt].ne=head[u];
    head[u]=cnt;
    edg[cnt].w=w;
    ++cnt;
    edg[cnt].to=u;
    edg[cnt].ne=head[v];
    head[v]=cnt;
    edg[cnt].w=0;
}

int d[N*100],S,T;

int rt[N],tot;

struct T{
    int ls,rs;
}t[N*31];

queue<int>q;

bool bfs()
{
    fill(d+S,d+T+1,-1);
    d[S]=0;
    q.push(S);
    for(int i=S;i<=T;i++)
        hd[i]=head[i];
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int tmp=head[x];tmp;tmp=edg[tmp].ne)
        {
            int v=edg[tmp].to;
            if(d[v]!=-1||!edg[tmp].w)
                continue;
            d[v]=d[x]+1;
            q.push(v);
        }
    }
    return d[T]!=-1;
}

int dinic(int x,int mn)
{
    if(!mn||x==T)
        return mn;
    int tmpf,flow=0;
    for(int &tmp=hd[x];tmp;tmp=edg[tmp].ne)
    {
        int v=edg[tmp].to;
        if(d[v]==d[x]+1&&(tmpf=dinic(v,min(mn,edg[tmp].w)))>0)
        {
            flow+=tmpf;
            mn-=tmpf;
            edg[tmp].w-=tmpf;
            edg[tmp^1].w+=tmpf;
        }
        if(!mn)
            break;
    }
    if(!flow)
        d[x]=-1;
    return flow;
}

vector<int>pt;

void ins(int x,int &y,int l,int r,int p)
{
    y=++tot;
    t[y]=t[x];
    if(x)
        build(y,x,1);
    if(l==r)
    {
        pt.push_back(y);
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)
        ins(t[x].ls,t[y].ls,l,mid,p);
    else
        ins(t[x].rs,t[y].rs,mid+1,r,p);
}

using pii=pair<int,int>;

pii blk[N];

void adde(int x,int l,int r,int L,int R,int f)
{
    if(!x)
        return;
    if(L<=l&&r<=R)
    {
        build(f,x,1e9);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid)
        adde(t[x].ls,l,mid,L,R,f);
    if(R>mid)
        adde(t[x].rs,mid+1,r,L,R,f);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&blk[i].first,&blk[i].second);
    sort(blk+1,blk+n+1);
    S=0;
    for(int i=1;i<=n;i++)
        ins(rt[i-1],rt[i],0,1e5,blk[i].second);
    for(int i=1;i<=tot;i++)
    {
        if(t[i].ls)
            build(i,t[i].ls,1e9);
        if(t[i].rs)
            build(i,t[i].rs,1e9);
    }
    scanf("%d",&m);
    T=tot+m+1;
    for(auto x:pt)
        build(x,T,1);
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        pii u;
        scanf("%d%d",&u.first,&u.second);
        build(S,tot+i,1);
        int p=upper_bound(blk+1,blk+n+1,u)-blk-1;
        adde(rt[p],0,1e5,0,u.second,tot+i);
        while(bfs())
            ans+=dinic(S,1e9);
        printf("%d\n",ans);
    }
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 3ms

memory: 9876kb

input:

output:

result:

ok 4 number(s): "1 2 2 3"

Test #2:

score: 0

Accepted

time: 1ms

memory: 9804kb

input:

output:

result:

ok 7 numbers

Test #3:

score: 0

Accepted

time: 3ms

memory: 9804kb

input:

output:

result:

ok 8 numbers

Test #4:

score: 0

Accepted

time: 2ms

memory: 9720kb

input:

output:

result:

ok 5 number(s): "1 1 2 3 4"

Test #5:

score: 0

Accepted

time: 0ms

memory: 9748kb

input:

output:

1
2

result:

ok 2 number(s): "1 2"

Test #6:

score: 0

Accepted

time: 1ms

memory: 9808kb

input:

output:

result:

ok 6 numbers

Test #7:

score: 0

Accepted

time: 4ms

memory: 11860kb

input:

output:

result:

ok 48 numbers

Test #8:

score: 0

Accepted

time: 4ms

memory: 9824kb

input:

output:

1
1

result:

ok 2 number(s): "1 1"

Test #9:

score: 0

Accepted

time: 3ms

memory: 9816kb

input:

output:

result:

ok 30 numbers

Test #10:

score: 0

Accepted

time: 1ms

memory: 9728kb

input:

output:

result:

ok 11 numbers

Test #11:

score: 0

Accepted

time: 1ms

memory: 9848kb

input:

output:

result:

ok 24 numbers

Test #12:

score: 0

Accepted

time: 0ms

memory: 9840kb

input:

output:

result:

ok 30 numbers

Test #13:

score: 0

Accepted

time: 0ms

memory: 11868kb

input:

output:

result:

ok 4 number(s): "1 2 3 4"

Test #14:

score: 0

Accepted

time: 1ms

memory: 9872kb

input:

output:

result:

ok 31 numbers

Test #15:

score: 0

Accepted

time: 1ms

memory: 11796kb

input:

output:

result:

ok 29 numbers

Test #16:

score: 0

Accepted

time: 4ms

memory: 9808kb

input:

output:

result:

ok 164 numbers

Test #17:

score: 0

Accepted

time: 3ms

memory: 9760kb

input:

output:

result:

ok 1 number(s): "1"

Test #18:

score: 0

Accepted

time: 12ms

memory: 11868kb

input:

output:

result:

ok 157 numbers

Test #19:

score: 0

Accepted

time: 7ms

memory: 9768kb

input:

output:

result:

ok 170 numbers

Test #20:

score: 0

Accepted

time: 4ms

memory: 11872kb

input:

output:

result:

ok 143 numbers

Test #21:

score: 0

Accepted

time: 2ms

memory: 11868kb

input:

output:

result:

ok 45 numbers

Test #22:

score: 0

Accepted

time: 6ms

memory: 11872kb

input:

output:

result:

ok 134 numbers

Test #23:

score: 0

Accepted

time: 2ms

memory: 11824kb

input:

output:

result:

ok 56 numbers

Test #24:

score: 0

Accepted

time: 4ms

memory: 9828kb

input:

output:

result:

ok 67 numbers

Test #25:

score: 0

Accepted

time: 3ms

memory: 13944kb

input:

output:

result:

ok 43 numbers

Test #26:

score: 0

Accepted

time: 10ms

memory: 9816kb

input:

output:

result:

ok 625 numbers

Test #27:

score: 0

Accepted

time: 117ms

memory: 11968kb

input:

output:

result:

ok 687 numbers

Test #28:

score: -100

Time Limit Exceeded

input:

output: