oj.uz

Submission #167853

# Submission time Handle Problem Language Result Execution time Memory
167853 2019-12-10T14:57:41 Z rzbt Plahte (COCI17_plahte) C++14
0 / 160
 2000 ms 70048 KB 
#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];
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()
{
    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++){
        jeste[cale[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);
        red.push(cale[t]);
    }
    for(int i=1;i<=n;i++)printf("%d\n",res[i].size());


    return 0;
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:80: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:26: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:29: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:36: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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 25804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 34028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 56792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 70048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 54552 KB Time limit exceeded
2 Halted 0 ms 0 KB -