제출 #329745

#제출 시각아이디문제언어결과실행 시간메모리
329745figter001팀들 (IOI15_teams)C++17
0 / 100
931 ms191804 KiB
#include "teams.h" #include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define fast ios::sync_with_stdio(false);cin.tie(0); typedef long long ll; typedef long double ld; typedef unsigned long long ull; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int nax = 5e5 + 100; struct node{ int l,r; ll sum; node(){ l = r = -1; sum = 0; } }seg[22*nax]; ll head[nax]; int T; void update(int n,int s,int e,int at,int val,int old){ if(s == e){ // cerr << n << ' ' << old << ' ' << seg[old].sum << '\n'; seg[n].sum += seg[old].sum + val; return; } if((s+e)/2 < at)seg[n].l = seg[old].l; else{ seg[n].l = ++T; update(seg[n].l,s,(s+e)/2,at,val,seg[old].l); } if((s+e)/2+1 > at)seg[n].r = seg[old].r; else{ seg[n].r = ++T; update(seg[n].r,(s+e)/2+1,e,at,val,seg[old].r); } seg[n].sum = seg[ seg[n].l ].sum + seg[ seg[n].r ].sum; // cerr << seg[n].sum << ' ' << s << ' ' << e << '\n'; } ll get(int n,int s,int e,int l,int r){ if(n <= 0)return 0; // assert(n >0); if(s > r || e < l || l > r)return 0; if(s >= l && e <= r)return seg[n].sum; return get( seg[n].l , s , (s+e)/2 , l , r ) + get( seg[n].r , (s+e)/2+1 , e , l , r); } // int main(){ // int cur = 1; // head[cur] = ++T; // build(head[1],1,n); // for(int i=0;i<q;i++){ // int t,k; // cin>>t>>k; // if(t == 1){//update // int at,val; // cin>>at>>val; // int old = head[k]; // head[k] = ++T; // update(head[k],1,n,at,val,old); // }else if(t == 2){//sum // int l,r; // cin>>l>>r; // cout << get(head[k],1,n,l,r) << endl; // }else if(t == 3){//make new // cur++; // head[cur] = head[k]; // } // } // } vector<pair<int,int>> s; int n; void init(int N, int A[], int B[]) { n = N; for(int i=0;i<n;i++)s.push_back({A[i], B[i]}); sort(all(s)); head[0] = ++T; int lst = T; for(int i=0;i<n;i++){ head[s[i].first] = ++T; update(head[s[i].first] , 1,n,s[i].second,1 + get(head[lst],1,n,s[i].second,s[i].second),lst); // cerr << ' ' << head[s[i].first] << ' ' << lst << ' ' << get(head[s[i].first],1,n,1,n) << '\n'; lst = head[s[i].first]; } for(int i=1;i<=n;i++){ if(head[i] == 0) head[i] = head[i-1]; } } int can(int M, int K[]) { // return 0; sort(K,K+M); int ex = 0; int lst = 0; vector<int> k; int id = 0; int sum = 0; for(int i=0;i<M;i++){ // int hv = get(head[lst],1,n,lst,K[i] - 1); // cerr << id << ' ' << k.size() << '\n'; // cerr << ' ' << lst << ' ' << K[i] << ' ' << hv << '\n'; while(id < k.size()){ if(get(head[k[id]],1,n,k[id],K[i] - 1) >= k[id]){ sum += k[id]; ex -= k[id]; id++; }else{ break; } // if(hv >= k[id]){ // hv-=k[id]; // ex -= k[id]; // id++; // }else{ // k[id] -= hv; // ex -= hv; // break; // } } lst = K[i]; ex += K[i]; // cerr << K[i] << ' ' << ex << ' ' << get(head[K[i]],1,n,K[i] , n) << '\n'; if(get(head[K[i]],1,n,K[i] , n) < ex){ // cerr << 0 << ' '; return 0; } k.push_back(K[i]); if(k[id] != K[i])return 0; } // cerr << 1 << ' '; return 1; }

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:91:61: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   update(head[s[i].first] , 1,n,s[i].second,1 + get(head[lst],1,n,s[i].second,s[i].second),lst);
      |                                                     ~~~~~~~~^
teams.cpp:91:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   update(head[s[i].first] , 1,n,s[i].second,1 + get(head[lst],1,n,s[i].second,s[i].second),lst);
      |          ~~~~~~~~~~~~~~~^
teams.cpp:91:47: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   update(head[s[i].first] , 1,n,s[i].second,1 + get(head[lst],1,n,s[i].second,s[i].second),lst);
      |                                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:93:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   93 |   lst = head[s[i].first];
      |         ~~~~~~~~~~~~~~~^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:113:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   while(id < k.size()){
      |         ~~~^~~~~~~~~~
teams.cpp:114:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  114 |    if(get(head[k[id]],1,n,k[id],K[i] - 1) >= k[id]){
      |           ~~~~~~~~~~^
teams.cpp:135:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  135 |   if(get(head[K[i]],1,n,K[i] , n) < ex){
      |          ~~~~~~~~~^
teams.cpp:105:6: warning: variable 'lst' set but not used [-Wunused-but-set-variable]
  105 |  int lst = 0;
      |      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...