Submission #167855

#	Time	Username	Problem	Language	Result	Execution time	Memory
167855		rzbt	Plahte (COCI17_plahte)	C++14	0 / 160	171 ms	10336 KiB

plahte

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 80005
typedef long long ll;

using namespace std;

int n,m;
int cale[MAXN],posecen[MAXN];
bool jeste[MAXN];
set<pair<int,int> > iznad;
vector<pair<pair<int,int> ,int> > query;

pair<pair<int,int>, pair<int,int> > prav[MAXN];

vector<int> res[MAXN];
queue<int> red;


int main()
{
    //freopen("input.txt","r",stdin);
    scanf("%d %d", &n, &m);
    for(int i=1;i<=n;i++){
        int x1,y1,x2,y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        prav[i]=(mp(mp(x1,y1),mp(x2,y2)));
        query.pb(mp(mp(x1,y1),i));
        query.pb(mp(mp(x2+1,-y2),i));
    }
    for(int i=1;i<=m;i++){
        int x,y,k;
        scanf("%d %d %d", &x, &y, &k);
        query.pb(mp(mp(x,y),-k));
    }
    sort(all(query));
    for(auto q:query){
        //printf("    %d %d   %d\n",q.F.F,q.F.S,q.S);
        if(q.S>0){
            if(q.F.S<0)iznad.erase(mp(-q.F.S,q.S));
            else{
                auto tcale=iznad.upper_bound(mp(prav[q.S].second.second,-1e9+7));
                if(tcale==iznad.end())cale[q.S]=0;
                else cale[q.S]=tcale->S;
                iznad.insert(mp(prav[q.S].second.second,q.S));
                //printf("                     %d\n",prav[q.S].second.second);

            }
        }else{
            auto ti=iznad.lower_bound(mp(q.F.S,-1e9+7));
            if(ti==iznad.end())continue;
            else res[ti->S].pb(-q.S);
        }

    }

    /*for(int i=1;i<=n;i++){
        printf("%d: ",i);
        for(auto x:res[i])printf("%d ",x);
        printf("\n");
    }*/
    for(int i=1;i<=n;i++){
        posecen[cale[i]]++;
        jeste[i]=true;
    }
    for(int i=1;i<=n;i++){
        if(!jeste[i])red.push(i);
    }
    while(!red.empty()){
        int t=red.front();

        red.pop();
        sort(all(res[t]));
        res[t].erase(unique(all(res[t])),res[t].end());
        if(cale[t]==0)continue;
        for(auto x:res[t])res[cale[t]].pb(x);
        posecen[cale[t]]--;
        if(!posecen[cale[t]])red.push(cale[t]);
    }
    for(int i=1;i<=n;i++)printf("%d\n",res[i].size());


    return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'int main()':
plahte.cpp:84:53: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     for(int i=1;i<=n;i++)printf("%d\n",res[i].size());
                                        ~~~~~~~~~~~~~^
plahte.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
plahte.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &x, &y, &k);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 32
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32