oj.uz

답안 #163926

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
163926 2019-11-16T09:07:04 Z TadijaSebez 절취선 (JOI14_ho_t5) C++11
0 / 100
 2 ms 380 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mt make_tuple
const int N=100050;
int X1[N],X2[N],Y1[N],Y2[N];
vector<tuple<int,int,int>> events;
int ls[N],rs[N],pri[N],val[N],tsz,root,sum[N],tag[N],fir[N],sz[N],L[N],R[N];
int Make(int v)
{
    tsz++;
    pri[tsz]=rand()^rand();
    val[tsz]=v;
    sz[tsz]=1;
    fir[tsz]=1;
    L[tsz]=R[tsz]=v;
    return tsz;
}
void upd(int x){ if(x) sum[x]=sz[x],fir[x]=0,tag[x]=1;}
void push(int x){ if(tag[x]) upd(ls[x]),upd(rs[x]),tag[x]=0;}
void pull(int x)
{
    sz[x]=sz[ls[x]]+1+sz[rs[x]];
    sum[x]=sum[ls[x]]+(1-fir[x])+sum[rs[x]];
    L[x]=ls[x]?L[ls[x]]:val[x];
    R[x]=rs[x]?R[rs[x]]:val[x];
}
void rot_l(int &x){ int y=rs[x],z=ls[y];rs[x]=z;ls[y]=x;pull(x);pull(y);x=y;}
void rot_r(int &x){ int y=ls[x],z=rs[y];ls[x]=z;rs[y]=x;pull(x);pull(y);x=y;}
void Ins(int &x, int v)
{
    if(!x) x=Make(v);
    else
    {
        push(x);
        if(val[x]<v)
        {
            Ins(rs[x],v);
            if(pri[rs[x]]>pri[x]) rot_l(x);
            else pull(x);
        }
        else
        {
            Ins(ls[x],v);
            if(pri[ls[x]]>pri[x]) rot_r(x);
            else pull(x);
        }
    }
}
int Get(int x, int qs, int qe)
{
    if(!x || L[x]>qe || R[x]<qs) return 0;
    if(L[x]>=qs && R[x]<=qe) return sum[x];
    push(x);
    return Get(ls[x],qs,qe)+Get(rs[x],qs,qe);
}
void Mark(int x, int qs, int qe)
{
    if(!x || L[x]>qe || R[x]<qs) return;
    if(L[x]>=qs && R[x]<=qe) return upd(x);
    push(x);
    Mark(ls[x],qs,qe);
    Mark(rs[x],qs,qe);
    pull(x);
}
int main()
{
    srand(time(0));
    int n,m,q;
    scanf("%i %i %i",&n,&m,&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%i %i %i %i",&X1[i],&Y1[i],&X2[i],&Y2[i]);
        if(X1[i]==X2[i]) events.pb(mt(X1[i],2,i));
        else events.pb(mt(X1[i],1,i)),events.pb(mt(X2[i],3,i));
    }
    sort(events.begin(),events.end());
    for(auto e:events)
    {
        int x,t,i;tie(x,t,i)=e;
        if(t==1)
        {
            
        }
        if(t==2)
        {
        }
        if(t==3)
        {
        }
    }
    return 0;
}

Compilation message

2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i %i %i",&n,&m,&q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i %i %i %i",&X1[i],&Y1[i],&X2[i],&Y2[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -