oj.uz

답안 #698771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
698771 2023-02-14T09:37:23 Z vjudge1 새 집 (APIO18_new_home) C++17
5 / 100
 1595 ms 789640 KB 
#include<bits/stdc++.h>
#define maxn 350000
#define maxl 700000
#define bl 1500
using namespace std;
int n,k,q;
int x[maxn];
int a[maxn];
int b[maxn];
int t[maxn];
int l[maxn];
int y[maxn];
int ap[maxn];
bool fn[maxn];
int ans[maxn];
vector<pair<pair<int,int>,int> > v;
vector<pair<int,int> > c;
vector<int> cs;
bool cur[maxn];
int segp[4*maxl];
int segm[4*maxl];
int lc[4*maxl];
int rc[4*maxl];
int ord[bl];
multiset<int> ns[bl];
int cnt=1;
void clear_seg() {
    cnt=1;
    segp[0]=-1e8;
    segm[0]=0;
    lc[0]=rc[0]=0;
}
inline void create_children(int id,int l,int r) {
    if(lc[id]==0) {
        segp[cnt]=-1e8;
        segm[cnt]=0;
        lc[cnt]=rc[cnt]=0;
        lc[id]=cnt++;
    }
    if(rc[id]==0) {
        segp[cnt]=-1e8;
        segm[cnt]=0;
        lc[cnt]=rc[cnt]=0;
        rc[id]=cnt++;
    }
}
void update(int id,int l,int r,int p,int q,int a,int b) {
    int m=(l+r)/2;
    create_children(id,l,r);
    if(p<=l && r<=q) {
        if(b==1) segp[id]=max(segp[id],a+l-1);
        else segm[id]=max(segm[id],a+1-l);
    }
    if(q<l || r<p) {
        return;
    }
    update(lc[id],l,m,p,q,a,b);
    update(rc[id],m+1,r,p,q,a,b);
}
int dif(int id,int l,int r,int x) {
    if(id==0 && !(l==1 && r==1e8)) return 0;
    int cur=max(segp[id]+x-l,segm[id]+l-x);
    int m=(l+r)/2;
    if(x<=m) return max(cur,dif(lc[id],l,m,x));
    else  return max(cur,dif(rc[id],m+1,r,x));
}
int main() {
    scanf("%d %d %d",&n,&k,&q);
    for(int i=1;i<=n;i++) {
        scanf("%d %d %d %d",&x[i],&t[i],&a[i],&b[i]);
        v.push_back({{a[i],0},i});
        v.push_back({{b[i],2},i});
    }
    for(int i=1;i<=q;i++) {
        scanf("%d %d",&l[i],&y[i]);
        v.push_back({{y[i],1},n+i});
    }
    sort(v.begin(),v.end());
    /*for(int i=0;i<v.size();i++) {
        cout<<v[i].first.first<<" "<<v[i].first.second<<" "<<v[i].second<<endl;
    }*/
    for(int i=0;i<v.size();i+=bl) {
        int cnt=0;
        for(int j=i;j<v.size() && j<i+bl;j++) {
            int ind=v[j].second;
            if(ind<=n) {
                if(ap[t[ind]]==0) {
                    cur[t[ind]]=true;
                    ord[t[ind]]=cnt;
                    cs.push_back(cnt);
                    cnt++;
                }
                ap[t[ind]]++;
            }
        }
        for(int j=i-1;j>=0;j--) {
            int ind=v[j].second;
            if(ind<=n) {
                if(v[j].first.second==2) fn[ind]=true;
                else {
                    if(!fn[ind] && ap[t[ind]]==0) {
                        c.push_back({t[ind],x[ind]});
                    }
                }
            }
        }
        for(int j=i-1;j>=0;j--) {
            int ind=v[j].second;
            if(ind<=n) {
                if(v[j].first.second==2) fn[ind]=true;
                else {
                    if(!fn[ind] && ap[t[ind]]==0) {
                        if(ap[t[ind]]==0) cnt++;
                        ap[t[ind]]++;
                    }
                }
            }
        }
        if(cnt==k) {
            sort(c.begin(),c.end());
            clear_seg();
            for(int i=0;i<c.size();i++) {
                if(i==0 || c[i-1].first!=c[i].first) {
                    update(0,1,1e8,1,c[i].second,c[i].second-1,-1);
                }
                else {
                    update(0,1,1e8,c[i-1].second,c[i].second,c[i].second-1,-1);
                }
                if(i+1==c.size() || c[i+1].first!=c[i].first) {
                    update(0,1,1e8,c[i].second,1e8,1-c[i].second,1);
                }
                else {
                    update(0,1,1e8,c[i].second,c[i+1].second,1-c[i].second,1);
                }
            }

            for(int j=i-1;j>=0;j--) {
                int ind=v[j].second;
                if(ind<=n) {
                    if(v[j].first.second==2) fn[ind]=true;
                    else {
                        if(!fn[ind] && cur[t[ind]]) {
                            ns[ord[t[ind]]].insert(x[ind]);
                        }
                    }
                }
            }

            for(int j=i;j<v.size() && j<i+bl;j++) {
                int ind=v[j].second;
                if(ind<=n) {
                    //cout<<j<<" "<<ind<<" "<<ord[t[ind]]<<" "<<v[j].first.second<<endl;
                    if(v[j].first.second==2) ns[ord[t[ind]]].erase(ns[ord[t[ind]]].find(x[ind]));
                    else ns[ord[t[ind]]].insert(x[ind]);
                }
                else {
                    ind-=n;
                    //cout<<j<<" "<<ind<<" "<<v[j].first.second<<endl;
                    for(auto tip:cs) {
                        //cout<<"\t"<<tip<<" "<<ns[tip].size()<<endl;
                        if(ns[tip].size()==0) ans[ind]=-1;
                    }
                    if(ans[ind]!=-1) {
                        if(cnt==cs.size()) ans[ind]=0;
                        else ans[ind]=dif(0,1,1e8,l[ind]);
                        for(auto tip:cs) {
                            set<int>::iterator it=ns[tip].lower_bound(l[ind]);
                            //cout<<l[ind]<<" "<<(*it)<<endl;
                            int csur=1e8;
                            if(it!=ns[tip].end()) csur=min(csur,(*it)-l[ind]);
                            if(it!=ns[tip].begin()) {
                                it--;
                                csur=min(csur,l[ind]-(*it));
                            }
                            ans[ind]=max(ans[ind],csur);
                        }
                    }
                }
            }

        }
        else {
            for(int j=i;j<v.size() && j<i+bl;j++) {
                int ind=v[j].second;
                if(ind>n) {
                    ans[ind-n]=-1;
                }
            }
        }
        c.clear();
        for(int j=0;j<v.size() && j<i+bl;j++) {
            int ind=v[j].second;
            if(ind<=n) {
                cur[t[ind]]=false;
                ns[ord[t[ind]]].clear();
                ord[t[ind]]=0;
                ap[t[ind]]=0;
            }
        }
        cs.clear();
    }
    for(int j=1;j<=q;j++) printf("%d\n",ans[j]);
    return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i=0;i<v.size();i+=bl) {
      |                 ~^~~~~~~~~
new_home.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(int j=i;j<v.size() && j<i+bl;j++) {
      |                     ~^~~~~~~~~
new_home.cpp:122:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             for(int i=0;i<c.size();i++) {
      |                         ~^~~~~~~~~
new_home.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |                 if(i+1==c.size() || c[i+1].first!=c[i].first) {
      |                    ~~~^~~~~~~~~~
new_home.cpp:149:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |             for(int j=i;j<v.size() && j<i+bl;j++) {
      |                         ~^~~~~~~~~
new_home.cpp:164:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |                         if(cnt==cs.size()) ans[ind]=0;
      |                            ~~~^~~~~~~~~~~
new_home.cpp:183:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |             for(int j=i;j<v.size() && j<i+bl;j++) {
      |                         ~^~~~~~~~~
new_home.cpp:191:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |         for(int j=0;j<v.size() && j<i+bl;j++) {
      |                     ~^~~~~~~~~
new_home.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%d %d %d",&n,&k,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
new_home.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%d %d %d %d",&x[i],&t[i],&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d %d",&l[i],&y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 520 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 524 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 528 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 472 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 520 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 524 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 528 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 472 KB Output is correct
31 Runtime error 548 ms 762604 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1595 ms 789640 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 727 ms 778556 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 520 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 524 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 528 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 472 KB Output is correct
31 Runtime error 548 ms 762604 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 520 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 524 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 528 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 472 KB Output is correct
31 Runtime error 548 ms 762604 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -