oj.uz

Submission #616903

# Submission time Handle Problem Language Result Execution time Memory
616903 2022-08-01T07:36:37 Z 조영욱(#8505) Sweeping (JOI20_sweeping) C++17
10 / 100
 3289 ms 423940 KB 
#include <bits/stdc++.h>
using namespace std;

const int sz=2097152;
typedef pair<int,int> P;
set<P> seg[sz*2];
int n,m,q;
typedef pair<P,int> Pi;
vector<Pi> save;
vector<int> pr;
vector<int> all; //�� ����
const int INF=1e9+7;

void insert(int l,int r,P val,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return;
    }
    if (l<=nodel&&noder<=r) {
        auto iter=seg[node].end();
        vector<P> er;
        while (iter!=seg[node].begin()) {
            iter--;
            if ((*iter).second>=val.second) {
                er.push_back((*iter));
            }
            else {
                break;
            }
        }
        for(int i=0;i<er.size();i++) {
            seg[node].erase(er[i]);
        }
        seg[node].insert(val);
        return;
    }
    int mid=(nodel+noder)/2;
    insert(l,r,val,node*2,nodel,mid);
    insert(l,r,val,node*2+1,mid+1,noder);
}

int cal(int i,int t) {
    i+=sz;
    int ret=INF;
    while (i>0) {
        auto iter=seg[i].lower_bound(P(t,-1));
        if (iter!=seg[i].end())
            ret=min(ret,(*iter).second);
        i/=2;
    }
    return ret;
}

int main(void) {
    scanf("%d %d %d",&n,&m,&q);
    for(int i=0;i<m;i++) {
        int x,y;
        scanf("%d %d",&x,&y);
        save.push_back(Pi(P(x,y),0));
        pr.push_back(y);
    }
    for(int i=0;i<q;i++) {
        int type;
        scanf("%d",&type);
        all.push_back(type);
        if (type==1) {
            int p;
            scanf("%d",&p);
            all.push_back(p);
        }
        if (type==2) {
            int l;
            scanf("%d",&l);
            all.push_back(l);
        }
        if (type==4) {
            int a,b;
            scanf("%d %d",&a,&b);
            all.push_back(a);
            all.push_back(b);
            save.push_back(Pi(P(a,b),i));
            pr.push_back(b);
        }
    }
    sort(pr.begin(),pr.end());
    pr.erase(unique(pr.begin(),pr.end()),pr.end());
    int ind=0;
    for(int i=0;i<q;i++) {
        int type=all[ind++];
        if (type==1) {
            int p=all[ind++];
            p--;
            int st=save[p].second;
            int yind=lower_bound(pr.begin(),pr.end(),save[p].first.second)-pr.begin();
            int mn=cal(yind,st);
            if (mn==INF||n-mn<save[p].first.first) {
                printf("%d %d\n",save[p].first.first,save[p].first.second);
            }
            else {
                printf("%d %d\n",n-mn,save[p].first.second);
            }
        }
        if (type==2) {
            int l=all[ind++];
            int yind=upper_bound(pr.begin(),pr.end(),l)-pr.begin()-1;
            if (yind>=0)
            insert(0,yind,P(i,l));
        }
        if (type==4) {
            int a=all[ind++];
            int b=all[ind++];
        }
    }
}

Compilation message

sweeping.cpp: In function 'void insert(int, int, P, int, int, int)':
sweeping.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(int i=0;i<er.size();i++) {
      |                     ~^~~~~~~~~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:109:17: warning: unused variable 'a' [-Wunused-variable]
  109 |             int a=all[ind++];
      |                 ^
sweeping.cpp:110:17: warning: unused variable 'b' [-Wunused-variable]
  110 |             int b=all[ind++];
      |                 ^
sweeping.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d %d %d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf("%d",&type);
      |         ~~~~~^~~~~~~~~~~~
sweeping.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |             scanf("%d",&p);
      |             ~~~~~^~~~~~~~~
sweeping.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |             scanf("%d",&l);
      |             ~~~~~^~~~~~~~~
sweeping.cpp:77:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |             scanf("%d %d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 197472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2466 ms 255756 KB Output is correct
2 Correct 2484 ms 276096 KB Output is correct
3 Correct 2575 ms 275820 KB Output is correct
4 Correct 3289 ms 423940 KB Output is correct
5 Correct 1550 ms 258176 KB Output is correct
6 Correct 2533 ms 271452 KB Output is correct
7 Correct 2546 ms 274544 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2634 ms 248308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 2634 ms 248308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 197472 KB Output isn't correct
2 Halted 0 ms 0 KB -