Submission #72422

#TimeUsernameProblemLanguageResultExecution timeMemory
72422김동현보다 잘함 (#118)Easy Data Structure Problem (FXCUP3_easy)C++17
0 / 100
5 ms2680 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; int INF = 1e8; int n, m; int tree[270000], key; int st[270000], en[270000]; vector<pii> lis[100100]; void init() { int i; for (key=1;key<n;key*=2); for (i=1;i<key*2;i++) tree[i] = INF; for (i=key;i<key*2;i++) st[i] = en[i] = i-key; for (i=key-1;i;i--) { st[i] = min(st[i*2],st[i*2+1]); en[i] = max(en[i*2],en[i*2+1]); } } void upd(int idx, int val) { idx += key; while(idx) { tree[idx] = min(tree[idx],val); idx/=2; } } void calc() { int i; for (i=1;i<key+n;i++) { if (en[i]<n) lis[tree[i]].push_back(pii(st[i],en[i])); } for (i=0;i<n;i++) { sort(lis[i].begin(),lis[i].end()); //printf("%d : ",i); //for (pii &v :lis[i]) printf("%d, %d ",v.first, v.second); //printf("\n"); } } int arr[100100]; int loc[100100]; vector<int> vec; vector<pii> cur; void solve() { cur.clear(); sort(vec.begin(),vec.end(),[](int a, int b){return loc[a]<loc[b];}); int i, a, b; for (i=0;i<lis[vec[0]].size();i++) cur.push_back(lis[vec[0]][i]); for (i=1;i<vec.size();i++) { sort(cur.begin(),cur.end(),[](pii a, pii b){return a.second<b.second;}); a = b = 0; vector<pii> tmp; while(a<cur.size()&&b<lis[vec[i]].size()) { if (cur[a].second+1<lis[vec[i]][b].first) a++; else if (cur[a].second+1>lis[vec[i]][b].first) b++; else { tmp.push_back(pii(cur[a].first,lis[vec[i]][b].second)); b++; } } cur = tmp; } if (cur.empty()) { printf("-1\n"); } else { printf("%d %d\n",cur[0].first+1,cur[0].second+1); } } int main() { int i, j; scanf("%d%d",&n,&m); init(); for (i=0;i<n;i++) { scanf("%d",&arr[i]); arr[i]--; loc[arr[i]] = i; upd(i,arr[i]); } calc(); for (i=0;i<m;i++) { int c; scanf("%d",&c); vec.clear(); for (j=0;j<c;j++) { int a; scanf("%d",&a); --a; vec.push_back(a); } solve(); } return 0; }

Compilation message (stderr)

easy.cpp: In function 'void solve()':
easy.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[vec[0]].size();i++) cur.push_back(lis[vec[0]][i]);
              ~^~~~~~~~~~~~~~~~~~~
easy.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=1;i<vec.size();i++) {
              ~^~~~~~~~~~~
easy.cpp:58:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(a<cur.size()&&b<lis[vec[i]].size()) {
               ~^~~~~~~~~~~
easy.cpp:58:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(a<cur.size()&&b<lis[vec[i]].size()) {
                             ~^~~~~~~~~~~~~~~~~~~
easy.cpp: In function 'int main()':
easy.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
easy.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[i]); arr[i]--;
         ~~~~~^~~~~~~~~~~~~~
easy.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&c);
         ~~~~~^~~~~~~~~
easy.cpp:93:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a); --a;
             ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...