QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#381527#7436. Optimal Ordered Problem Solvermarher0 1293ms234452kbC++146.0kb2024-04-07 18:36:562024-04-07 18:36:57

Judging History

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

  • [2024-04-07 18:36:57]
  • 评测
  • 测评结果:0
  • 用时:1293ms
  • 内存:234452kb
  • [2024-04-07 18:36:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+200;

namespace IO {
#define iL (1 << 20)
char ibuf[iL], *iS = ibuf + iL, *iT = ibuf + iL;
#define gc() ((iS == iT) ? (iT = (iS = ibuf) + fread(ibuf, 1, iL, stdin), iS == iT ? EOF : *iS ++) : *iS ++)
template<class T> inline void read(T &x) {
  x = 0;int f = 0;char ch = gc();
  for (; !isdigit(ch); f |= ch == '-', ch = gc());
  for (; isdigit(ch); x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc());
  x = (f == 1 ? ~ x + 1 : x);
}
template<class T, class... Args> inline void read(T &x, Args&... args) { read(x), read(args...); }
template<class T> inline void readch(T &x) { char ch = gc(); for (; !isalpha(ch); ch = gc()); x = ch; }
char Out[iL], *iter = Out;
#define flush() fwrite(Out, 1, iter - Out, stdout), iter = Out
template<class T> inline void write(T x, char ch = '\n') {
  T l, c[35];
  if (x < 0) *iter ++ = '-', x = ~ x + 1;
  for (l = 0; !l || x; c[l] = x % 10, l++, x /= 10);
  for (; l; -- l, *iter ++ = c[l] + '0');*iter ++ = ch;
  flush();
}
template<class T, class... Args> inline void write(T x, Args... args) { write(x, ' '), write(args...); }
} // IO
using namespace IO;

struct poi
{
    int x,y;

    friend bool operator<(poi a,poi b)
    {
        return a.y==b.y?a.x<=b.x:a.y<b.y;
    }

    int in(poi t)
    {
        return (t.x>=x)&(t.y>=y);
    }
}a[N];

struct node
{
    poi l,r,w,la;int opt,siz,rd;

    void mk(poi d,int o)
    {
        if(o&1)opt|=1,l.y=r.y=w.y=la.y=d.y;
        if(o&2)opt|=2,l.x=r.x=w.x=la.x=d.x;
    }
}t[N];

int n,m,pos[N],vis[N],ans[N],mx[N],ch[N][2],tot,ro,now;
vector<int>p[N];

#define ls ch[x][0]
#define rs ch[x][1]

void up(int x)
{
    t[x].l=ls?t[ls].l:t[x].w;
    t[x].r=rs?t[rs].r:t[x].w;
    t[x].siz=t[ls].siz+t[rs].siz+1;
}

int make_new(poi w)
{
    int x=++tot;
    t[x]=(node){w,w,w,(poi){},0,1,rand()};
    return x;
}

void down(int x)
{
    if(!t[x].opt)return;
    if(ls)t[ls].mk(t[x].la,t[x].opt);
    if(rs)t[rs].mk(t[x].la,t[x].opt);
    t[x].opt=0;
}

void split(int x,poi k,int&a,int&b)
{
    if(!x)a=b=0;
    else
    {
        down(x);
        if(t[x].w<k)a=x,split(rs,k,rs,b);
        else b=x,split(ls,k,a,ls);
        up(x);
    }
}

int merge(int a,int b)
{
    if(!a||!b)return a+b;
    int w;down(a),down(b);
    if(t[a].rd<t[b].rd)ch[a][1]=merge(ch[a][1],b),up(a),w=a;
    else ch[b][0]=merge(a,ch[b][0]),up(b),w=b;
    return w;
}

void add(poi x)
{
    int a=0,b=0;
    split(ro,x,a,b);
    ro=merge(merge(a,make_new(x)),b);
}

void dfs(int x,poi d,int opt)
{
    if(!x)return;
    if(t[x].l.in(d)&&t[x].r.in(d))return t[x].mk(d,opt);
    if(t[x].r.y>d.y||t[x].l.x>d.x)return;
    down(x);dfs(ls,d,opt);dfs(rs,d,opt);
    if(t[x].w.in(d))
    {
        if(opt==1)t[x].w.y=d.y;
        else t[x].w.x=d.x;
    }
    up(x);
}

int find(int x,poi d)
{
    if(!x)return 0;
    if(t[x].l.in(d)&&t[x].r.in(d))return t[x].siz;
    if(t[x].r.y>d.y||t[x].l.x>d.x)return 0;
    down(x);return find(ls,d)+find(rs,d)+t[x].w.in(d);
}

void findd(int x,poi d)
{
    if(!x)return;
    if(t[x].r.y>d.y||t[x].l.x>d.x)return;
    down(x);find(ls,d);
    if(t[x].w.in(d))cout<<t[x].w.x<<' '<<t[x].w.y<<'\n';
    find(rs,d);
}

void insert(int d,int x)
{
    for(int i=d;i<=n;i+=(i&(-i)))p[i].push_back(x);
}

void rinsert(int x,int y)
{
    x=n-x+1;
    for(int i=x;i<=n;i+=(i&(-i)))mx[i]=max(mx[i],y);
}

int rfind(int x)
{
    x=n-x+1;int ans=0;if(x<0)return 0;
    for(int i=x;i;i-=(i&(-i)))ans=max(ans,mx[i]);
    return ans;
}

struct tree
{
    int p[N];

    void insert(int x,int d)
    {
        for(int i=x;i<=n;i+=(i&(-i)))p[i]+=d;
    }

    int find(int x)
    {
        int ans=0;
        for(int i=x;i;i-=(i&(-i)))ans+=p[i];
        return ans;
    }
}xx,yy,pp;

void ad(int x,int y,int opt)
{
    for(int i=1;i<=n;i++)if(a[i].in((poi){x,y}))
    {
        if(opt==1)a[i].y=y;
        else a[i].x=x;
    }
}

void add(int x,int y,int opt)
{
    ad(x,y,opt);
    rinsert(x,y);dfs(ro,(poi){x,y},opt);
    for(int i=x;i;i-=(i&(-i)))
    {
        int&d=pos[i];
        while(d<p[i].size()&&a[p[i][d]].y<=y)
        {
            if(vis[p[i][d]]){d++;continue;}
            vis[p[i][d]]=1;auto r=a[p[i][d]];
            xx.insert(r.x,-1),yy.insert(r.y,-1);
            if(opt==1)r.y=y;else r.x=x;
            add(r);d++;--now;
        }
    }
}

vector<pair<int,int>>ask[N];

void ddfs(int x)
{
    if(!x)return;
    cout<<x<<' '<<t[x].siz<<' '<<ls<<' '<<rs<<' '<<t[x].w.x<<' '<<t[x].w.y<<' '<<t[x].l.x<<' '<<t[x].l.y<<' '<<t[x].r.x<<' '<<t[x].r.y<<'\n';
    down(x);ddfs(ls);ddfs(rs);
}

int main()
{
    // freopen("in","r",stdin);
    read(n,m);now=n;
    for(int i=1;i<=n;i++)read(a[i].x,a[i].y),xx.insert(a[i].x,1),yy.insert(a[i].y,1);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)insert(a[i].x,i);
    for(int i=1;i<=m;i++)
    {
        int opt,x,y,X,Y;read(opt,x,y,X,Y);
        add(x,y,opt);if(rfind(X+1)>Y)continue;
        ans[i]=find(ro,(poi){X,Y})+xx.find(X)+yy.find(Y)-now;
        int res=0,rx=0;
        for(int j=1;j<=n;j++)
        {
            if(vis[j])res+=a[j].in((poi){X,Y});
            else rx+=a[j].x<=X,rx+=a[j].y<=Y;
        }
        if(ans[i]!=res+rx-now)
        {
            cout<<i<<'\n'<<res<<' '<<find(ro,(poi){X,Y})<<'\n'<<rx<<' '<<xx.find(X)+yy.find(Y)<<'\n'<<now<<'\n'<<X<<' '<<Y<<'\n'<<'\n';
            findd(ro,(poi){X,Y});
            puts("");
            for(int j=1;j<=n;j++)if(vis[j])
            {

            if(a[j].in((poi){X,Y}))cout<<"1 "<<a[j].x<<' '<<a[j].y<<'\n';
            else cout<<"2 "<<a[j].x<<' '<<a[j].y<<'\n';
            }
            puts("\n");
            ddfs(ro);
            return 0;
        }
        ask[Y].push_back(make_pair(X,i));
    }
    for(int i=n,pos=n;i>=1;i--)
    {
        for(auto x:ask[i])ans[x.second]+=pp.find(n-x.first);
        while(pos&&a[pos].y==i)pp.insert(n-a[pos--].x+1,1);
    }
    for(int i=1;i<=m;i++)write(ans[i]);
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 11ms
memory: 113384kb

input:

995 996
950 481
376 18
141 776
711 966
130 727
468 529
47 39
857 563
832 821
776 472
154 914
825 279
332 415
470 361
968 440
45 560
299 755
703 785
744 387
547 382
3 549
344 573
778 424
784 765
280 115
251 434
695 98
463 506
379 38
610 486
305 623
703 244
856 365
117 360
772 847
331 723
663 991
900 ...

output:

26
2 4
111 112
991
34 76

34 23

2 39 20
1 34 23
2 39 20
1 34 23


2 4 3 1 34 23 34 20 34 23
3 2 0 4 34 20 34 20 34 20
4 1 0 0 34 20 34 20 34 20
1 1 0 0 34 23 34 23 34 23

result:

wrong answer 1st numbers differ - expected: '423', found: '26'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 1293ms
memory: 234452kb

input:

999996 999996
921339 140126
955508 363759
958698 342406
280137 955674
907511 75721
189876 946586
152058 168837
541857 557702
84498 865987
185574 809224
704828 701026
815379 548000
989515 518951
335439 336866
745570 790616
766723 212893
926629 859003
51261 40866
592510 556235
324926 700261
320946 798...

output:

6
331382 0
494676 654529
321715
926136 888842


1 754876 3
1 754876 5
1 754876 6
1 754876 6
1 754876 7
1 754876 7
1 754876 12
1 754876 14
1 754876 14
1 754876 16
1 754876 17
1 754876 18
1 754876 19
1 754876 21
1 754876 21
1 754876 23
1 754876 23
1 754876 26
1 754876 28
1 754876 29
1 754876 31
1 7548...

result:

wrong answer 1st numbers differ - expected: '0', found: '6'

Subtask #3:

score: 0
Wrong Answer

Test #17:

score: 0
Wrong Answer
time: 456ms
memory: 195324kb

input:

999995 999997
261379 334440
985281 986034
549380 718157
670003 253925
533027 437989
326806 983213
965935 756259
229069 686789
331338 684961
957559 390618
937820 959719
338153 779814
582581 965418
634156 421264
308778 938878
913059 390904
481477 431492
739774 793015
901442 934600
256704 991485
366691...

output:

4
0 0
1288690 1288692
999992
963354 325562


2 2 330217
2 1 805517
2 1 805517


2 3 3 0 1 805517 2 330217 1 805517
3 2 0 1 2 330217 2 330217 1 805517
1 1 0 0 1 805517 1 805517 1 805517

result:

wrong answer 1st numbers differ - expected: '160635', found: '4'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%